307 Range Sum Query - Mutable

307. Range Sum Query - Mutable

1. Question

Given an integer arraynums, find the sum of the elements between indicesiandj(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.

2. Implementation

(1) Binary Index Tree

class NumArray {
    BIT bit;
    int[] nums;
    int size;

    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return ;
        }
        size = nums.length;
        this.nums = nums;
        bit = new BIT(size);

        for (int i = 0; i < size; i++) {
            bit.update(i + 1, nums[i]);
        }
    }

    public void update(int i, int val) {
        bit.update(i + 1, val - nums[i]);
        nums[i] = val;
    }

    public int sumRange(int i, int j) {
        return bit.query(j + 1) - bit.query(i);
    }
}

class BIT {
    int[] sums;

    public BIT(int n) {
        sums = new int[n + 1];
    }

    public void update (int index, int val) {
        while (index < sums.length) {
            sums[index] += val;
            index += index & -index;
        }
    }

    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += sums[index];
            index -= index & -index;
        }
        return sum;
    }
}

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

3. Time & Space Complexity

Binary Indexed Tree: 时间复杂度: Binary Indexed Tree构造O(NlogN), update(logN), sumRange(logN), 空间复杂度O(N)