307. Range Sum Query - Mutable

Problem:

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

6/27/2018 update:
In sum function, j has to greater than 0, otherwise it will fall into infinite loop. Because 0's lowBit is 0.
--------------------------------------------------------------------------------------------------------------------------
Analysis:
用Binary index tree做。好难啊，看了一晚上。
参见：http://www.cnblogs.com/grandyang/p/4985506.html

Solution：
Inorder to merge initialization and update, we need to create another array as member of the NumArray class.  If we still use nums in update, when initializing BIT, the diff would be 0.

class NumArray {
    int[] num;
    int[] BIT;
    int n;
    public NumArray(int[] nums) {
        n = nums.length;
        this.num = new int[n];
        this.BIT = new int[n + 1];
        for (int i = 0; i < n; i++) {
            update(i, nums[i]);
        }
    }
    
    public void update(int i, int val) {
        int diff = val - num[i];
        num[i] = val;
        for (int j = i + 1; j <= n; j += lowBit(j)) {
            BIT[j] += diff;
        }
    }
    
    public int sumRange(int i, int j) {
        return sum(j + 1) - sum(i);
    }
    
    private int sum(int i) {
        int sum = 0;
        for (int j = i; j > 0; j -= lowBit(j)) {
            sum += BIT[j];
        }
        return sum;
    }
    
    private int lowBit(int i) {
        return i & (-i);
    }
}

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