Range Sum Query - Mutable

Question

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.

Analysis:

Binary Indexed Tree Approach

Solution:

public class NumArray {
/*
Fenwick tree (aka Binary indexed tree):
http://www.algorithmist.com/index.php/Fenwick_tree
*/
    int[] tree;
    int[] nums;
    int size;
    public NumArray(int[] nums) {
        this.size = nums.length;
        this.nums = new int[size];
        this.tree = new int[size+1];
        for (int i = 0; i < size; i++)  update(i, nums[i]);
    }

    public void update(int i, int val) {
        int delta = val - nums[i];
        nums[i] = val;
        for(int index = i+1; index<=size; index+=index&(-index)){
            tree[index]+=delta;
        }
    }

    public int sumRange(int i, int j) {
        return sum(j) - sum(i - 1);
    }

    public int sum(int ind) {
        int ans = 0;
        for(int index=ind+1; index>0; index-=index&(-index)){
            ans += tree[index];
        }
        return ans;
    }
}