307

class NumArray {
public:
    vector<int> bit;
    int n;
    NumArray(vector<int>& nums) {
        n = nums.size();
        bit.resize(n+1, 0);
        for(int i=0; i<nums.size(); i++)
            update(i, nums[i]);
    }

    void update(int index, int val) {
        index++;
        int oldVal = sumRange(index-1, index-1);
        val = val-oldVal;
        while(index<=n){
            bit[index] += val;
            index += (index & -index);
        }
    }

    int sumRange(int left, int right) {
        int sum = 0;
        right++;
        while(right > 0){
            sum += bit[right];
            right -= (right & -right);
        }

        while(left > 0){
            sum -= bit[left];
            left -= (left & -left);
        }
        return sum;
    }
};

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