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.

一刷
題解：BinaryIndexTree
注意，在binaryIndexTree中，0是不用的,否則0get parent會一直停在0，陷入死循環(huán)，從1開始。所以int[] dp = new int[len+1]

class NumArray {
    int[] dp;
    int[] nums;
    int n;
    public NumArray(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        dp = new int[this.n+1];
        for(int i=0; i<nums.length; i++){
            init(i+1, nums[i]);
        }
    }
    
    private void init(int i, int val){
        while(i<=n){
            dp[i] += val;
            i += (i&-i);
        }
    }
    
    public void update(int i, int val) {
        int delta = val - nums[i];
        nums[i] = val;
        for(int j=i+1; j<dp.length; j+= j&(-j)){
            dp[j] += delta;
        }
    }
    
    public int sumRange(int i, int j) {
        return getSum(j+1) - getSum(i);
    }
    
    private int getSum(int index){
        int res = 0;
        while(index>=1){
            res += dp[index];
            index -= index & (-index);
        }
        return res;
    }
}

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