0307. Range Sum Query - Mutable.md

307. Range Sum Query - Mutable, medium

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 Note:

The array is only modifiable by the update function. You may assume the number of calls to update and sumRange function is distributed evenly.

["NumArray","update","update","update","sumRange","update","sumRange","update","sumRange","sumRange","update"] [[[7,2,7,2,0]],[4,6],[0,2],[0,9],[4,4],[3,8],[0,4],[4,1],[0,3],[0,4],[0,4]] ["NumArray","sumRange","update","sumRange"] [[[1,3,5]],[0,2],[1,2],[0,2]]

// 36ms, 81%
class NumArray {
private:
    vector<int> ar;
    vector<int> arbits;
public:
    NumArray(vector<int>& nums) {
        ar = nums;
        arbits.resize(nums.size()+1);
        for (int i = 0; i < nums.size(); i++) {
            update_delta(i+1, nums[i]);
        }
    }
    // j starts from 1 to N
    void update_delta(int j, int delta) {
        for (; j < arbits.size(); j += j & -j) {
            arbits[j] += delta;
        }
    }
    // j starts from 1 to N
    int query(int j) {
        int sum = 0;
        for (; j > 0; j -= j & -j) {
            sum += arbits[j];
        }
        return sum;
    }
    void update(int i, int val) {
        update_delta(i+1, val - ar[i]);
        ar[i] = val;
    }
    
    int sumRange(int i, int j) {
        return query(j+1) - query(i);
    }
};

/**
 * 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);
 */