leetCode-307:Range Sum Query - Mutable

问题描述

给定一个整数数组，数组中元素可以发生改变，要求多次查询数组中的区间和。题目链接：**点我**

样例输入输出

输入：

[“NumArray”, “sumRange”, “update”, “sumRange”]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]

输出：[null, 9, null, 8]

解释：

NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

问题解法

此题最简单的做法是每次根据查询的区间进行求和，但是这样时间复杂度过高。优化的方式是使用树状数组，将原始数组元素转成树状数组，每次更新原始元素的值时同时更新树状数组受影响的元素。这样每次查询时可以使用 log(k) 的时间复杂度，比刚开始直接区间遍历要快得多。代码如下：

class NumArray {
    int[] nums;

    int[] sums;

    public NumArray(int[] nums) {
        this.nums = new int[nums.length];
        sums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            update(i, nums[i]);
        }
    }

    public void update(int index, int val) {
        int increaseNum = val - nums[index];
        nums[index] = val;
        for (int i = index + 1; i < sums.length; i += lowBit(i)) {
            sums[i] += increaseNum;
        }
    }

    public int sumRange(int left, int right) {
        return querySum(right + 1) - querySum(left);
    }

    private int querySum(int index) {
        int sum = 0;
        for (int i = index; i > 0; i -= lowBit(i)) {
            sum += sums[i];
        }

        return sum;
    }

    private int lowBit(int n) {
        return n & (-n);
    }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */