Wednesday, February 3, 2016

307. Range Sum Query - Mutable ----------M

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

 

Constraints:

  • The array is only modifiable by the update function.
  • You may assume the number of calls to update and sumRange function is distributed evenly.
  • 0 <= i <= j <= nums.length - 1
A:

class NumArray {
public:
    NumArray(vector<int>& nums) {
        V = nums;
        for(int i =1;i<V.size();i++)
            V[i] += V[i-1];
    }
    
    void update(int i, int val) {
        int diff = val -  (V[i] - (i==0? 0 : V[i-1]));
        for(;i<V.size(); i++){
            V[i] += diff;
        }
    }
    
    int sumRange(int i, int j) {
        return V[j] - (i==0? 0:V[i-1]);
    }
private:
    vector<int> V;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */



Mistakes:


No comments:

Post a Comment