Simple Method using sum-array and beats 100% answer~~~~~


  • -1
    X

    just store the sum array in the construction func and update the [i,n] elem in the update func
    the search consume O(1) and the update func would consume O(n) in worest casess
    Don't need to talk too much just show the code

    class NumArray {
    public:
        vector<int> sumn;
        NumArray(vector<int> &nums) {
            sumn.push_back(0);
            int sum =0;
            int sz = nums.size();
            for (int i = 0; i<sz; i++) {
                sum += nums[i];
                sumn.push_back(sum);
            }
        }
        void update(int i, int val) {
            int tmp = sumn[i+1] - sumn[i];
            for (int j=i+1;j<sumn.size(); j++) {
                sumn[j] = sumn[j] - tmp + val;
            }
        }
        
        int sumRange(int i, int j) {
            return sumn[j+1] - sumn[i];
    
        }
    };

  • 0

    No, it is TLE.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.