Range Sum Query - Mutable

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.

Update 2016-11-12

I reviewed binary index tree again and found this interesting post, so this update is an explanation in English. All credits give to the original post.

The idea is to transfer the search index to binary format, each layer represents the lowest bit of the index number:

For example, the lowbit, which is the lowest bit 1 in the number, of 3 is 1 because the binary format of 3 is 11. The lowbit of 8 is 8 because the binary format of 8 is 1000, so the lowest bit is also the highest bit, which is itself. 

Lowbit of a number can be calculated by x&(-x) because in the binary format, negative format of a number is calculated by two's complement. For example, in a 8 bit representation, 4210 = 001010102, -4210 = 110101102 = 1 highest bit as sign + (~42 + 1). So the lowest bit of 42 is 2 (10 in binary). Now we can construct the tree based on bits:

Every row represents the layer of lowbit, every column represents the index in the array. As we can see on the chart, every higher bit index stores sum of itself and all its left children. For example, 4 is a higher bit then 2 and 1, it stores the sum of v1 to v4. 5 has lowbit 1, so it doesn't have any left children, and it only stores value of itself. Now it becomes easier to understand the following initialization code: for each index, we need to update the value of itself and all its right parent's value. Updating the structure means we add the difference to the index and all its right parent. 

Since each index only takes care of the value itself and all its left children, when we need to find the sum of an index, we need to add all its left parent's value. For example, if we want to find sum of index 5, we need to get the value of index 5 and its left parent, which is index 4. So what we need to do is to sum up its index and index - lowbit of itself. 

So the total initialization and search complexity are O(nlogn) and O(logn). 

Naturally I would think of using the same approach as we did in the immutable ones (i.e., using a "sum" array). However, if we do that way, the update will take too long time that it will exceed time limit.

I searched a little bit, and found this interesting data structure: Fenwick tree. I haven't fully understand how it works. But in short, we need a helper array, say bit[], each element i is responsible for nums[i - 1] and all elements that are smaller than the least bit of 1 i.e., (i&-i). The way we calculate it is for each nums[i - 1], we add nums[i - 1] to each i where i = i + (i&-i).

private void init(int pos, int val) {
        while (pos < bit.length) {
            bit[pos] += val;
            pos += (pos & -pos);
        }
    }


Now comes the sum part, reversely, sum += bit[i + 1], then i = i - (i&-i). However, this is the part that I don't quite understand. At least it works.

public class NumArray {
    private int[] bit;
    private int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;
        bit = new int[nums.length + 1];
        bit[0] = 0;
        for (int i = 1; i <= nums.length; i++) {
            init(i, nums[i - 1]);
        }
        
    }
    
    private void init(int pos, int val) {
        while (pos < bit.length) {
            bit[pos] += val;
            pos += (pos & -pos);
        }
    }

    void update(int i, int val) {
        int difference = val - nums[i];
        init(i + 1, difference);
        nums[i] = val;
    }

    public int sumRange(int i, int j) {
        return getSum(j + 1) - getSum(i);
    }
    
    private int getSum(int i) {
        int sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= (i&-i);
        }
        return sum;
    }
    
}