Range Sum Query – Mutable

求range sum, fenwick tree.

class NumArray {
    int[] nums;
    int[] BIT;
    public int lowbit(int x) {
        return x&(-x);
    }
    
    public void set(int i, int val){
        i++;
        while(i <= nums.length){
            BIT[i] += val;
            i += lowbit(i);
        }
    }
     
    public NumArray(int[] nums) {
        this.nums = nums;
        this.BIT = new int[nums.length + 5];
        for(int i = 0; i < nums.length; i++)
            set(i, nums[i]);
    }
    
    public void update(int index, int val) {
        int diff = val - nums[index];
        nums[index] = val;
        set(index, diff);
    }
    
    public int sumRange(int left, int right) {
        return sum(right) - sum(left - 1);
    }
    
    public int sum(int i){
        int s = 0;
        i++;
        while(i > 0){
            s += BIT[i];
            i -= lowbit(i);
        }
        return s;
    }
}

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