Leetcode 307. 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: The array is only modifiable by the update function. You may assume the number of calls to update and sumRange function is distributed evenly. Show Tags Show Similar Problems

思路

这道题是1d mutable subarray sum query，没办法这道题的优化解只能通过构造树状数据结构得出,either segment tree or binary indexed tree。这里我们使用binary indexed tree，因为实现起来方便。要想理解BIT，主要就是理解三个部分，初始化BIT，add(index, value), getSum(index)。

初始化的过程就是不断用二进制表示的index去填充BIT的prefix sum slot。这里的视频讲解的非常到位。https://www.youtube.com/watch?v=v_wj_mOAlig&index=2&list=PLZ_pfgKiIBrTdUKevYPsS0c7jAhgkPb6e

add()就是在当前index上不断往右边的parent走，具体到算法就是add last set bit <=> index += (index) & (-index)

getSum()就是在当前index上不断往左parent走，具体到算法就是remove last set bit <=> index -= (index) & (-index)

注意这里BITree的起始点是1，所以我们需要size + 1的数组来表示BITree，而且init tree就等于是对每一个element进行add operation。

复杂度

space O(n), add time O(logn), sum time O(logn)

代码

  public class NumArray {
    int[] BITree;
    int[] array;
    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int size = nums.length;
        BITree = new int[size + 1];
        array = nums;
        //init tree
        for (int i = 0; i < nums.length; i++) {
            add(i + 1, nums[i]);
        }
    }

    void update(int i, int val) {
        int diff = val - array[i];
        add(i + 1, diff);
        array[i] = val;
    }

    public int sumRange(int i, int j) {
        int shortArr = i == 0? 0 : getSum(i);
        int longArr = getSum(j + 1);
        return longArr - shortArr;
    }

    public void add(int index, int value) {
        while (index < BITree.length) {
            BITree[index] += value;
            index += (index) & (-index);
        }
    }

    public int getSum(int index) {
        int result = 0;
        while (index > 0) {
            result += BITree[index];
            index -= (index) & (-index);
        }
        return result;
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);