leetcode 307. Range Sum Query

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:

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

题解：树状数组最基本的用法（点更新，区间查询）。需要注意的是这里的点更新不是把点加一个值，而是完全更新一个点的值，这就需要不仅仅更新树状数组，原数组的值也应该更新，因为可能下一个还会更新这个点，那么就需要知道它之前的值是多少。

class NumArray {
public:
    NumArray(vector<int> &nums) {
        n = nums.size();
        c=vector<int>(n+1,0);
        a=vector<int>(n+1,0);
        for(int i=1;i<=n;i++){
            update(i-1,nums[i-1]);
        }
    }
    
    int lowbit(int x){
        return x&-x;
    }
    void update(int i, int val) {
        int old = a[i+1];
        for(int k=i+1;k<=n;k+=lowbit(k)){
            c[k]-=old;
            c[k]+=val;
        }
        a[i+1]=val;
    }
    int sum(int x){
        int s=0;
        while(x>0){
            s+=c[x];
            x-=lowbit(x);
        }
        return s;
    }

    int sumRange(int i, int j) {
        return sum(j+1)-sum(i);
    }
    
private:
    int n;
    vector<int>c;
    vector<int>a;
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);