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.

class NumArray {
    // A TreeNode stores sum of a range
    int[] tree, nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        tree = new int[4 * nums.length];
        if(nums.length==0)
            return;
        // O(N)
        buildTree(0, nums.length - 1, 1);
    }

    public void buildTree(int start, int end, int index) {
        if (start == end) {
            tree[index] = nums[start];
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(start, mid, 2 * index);
        buildTree(mid + 1, end, 2 * index + 1);
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }

    public void update(int i, int val) {
        // O(logN)
        update(0, nums.length - 1, 1, i, val);
    }

    public void update(int start, int end, int index, int updateIndex, int value) {
        if (start == end) {
            // At this point start == end == updateIndex
            nums[start] = tree[index] = value;
            return;
        }
        int mid = start + (end - start) / 2;
        // Right call
        if (updateIndex > mid)
            update(mid + 1, end, 2 * index + 1, updateIndex, value);
        // Left call
        else
            update(start, mid, 2 * index, updateIndex, value);
        // Reflect changes in parent node
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }

    public int sumRange(int i, int j) {
        return query(0, nums.length - 1, 1, i, j);
    }

    public int query(int start, int end, int index, int L, int R) {
        // No overlap
        if (start > R || end < L)
            return 0;
        // Complete overlap
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        int leftSum = query(start, mid, 2 * index, L, R);
        int rightSum = query(mid + 1, end, 2 * index + 1, L, R);
        return leftSum + rightSum;
    }
}