s4553711
5/25/2017 - 2:57 PM

307.cpp

class NumArray {
public:
    NumArray(vector<int> nums):term(nums) {
        bit.resize(nums.size()+1, 0);
        for(int i = 0; i < nums.size(); i++) {
            add(i+1, nums[i]);
        }
    }
    
    void update(int i, int val) {
        add(i+1, val-term[i]);
        term[i] = val;
    }
    
    int sumRange(int i, int j) {
        return sum(j+1) - sum(i);        
    }
    
    int sum(int index) {
        int ans = 0;
        while(index > 0) {
            ans += bit[index];
            index -= (index&-index);
        }
        return ans;
    }
    
    void add(int index, int d) {
        while(index <= term.size()) {
            bit[index] += d;
            index += (index&-index);
        }
    }
private:
    vector<int> bit;
    vector<int> term;
};

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