区域和检索 - 数组可修改

给你一个数组 nums ，请你完成两类查询。

1. 其中一类查询要求 更新 数组 nums 下标对应的值
2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right

实现 NumArray 类：

• NumArray(int[] nums) 用整数数组 nums 初始化对象
• void update(int index, int val) 将 nums[index] 的值 更新 为 val
• int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）

 

示例 1：

输入：
["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); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

 

提示：

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• 调用 update 和 sumRange 方法次数不大于 3 * 104 

/*
 * 题目思路：
 * 使用 Java Stream 的方法进行查询和更新操作。由于 Stream 不支持原地修改，因此我们仍然需要维护一个数组进行更新。
 * 在求和操作时，可以利用 Stream 的 range 方法进行范围查询。
 */
 
import java.util.stream.IntStream;
 
public class NumArrayStream {
    private int[] nums;
 
    public NumArrayStream(int[] nums) {
        this.nums = nums;
    }
 
    public void update(int index, int val) {
        nums[index] = val;
    }
 
    public int sumRange(int left, int right) {
        return IntStream.rangeClosed(left, right).map(i -> nums[i]).sum();
    }
}

这个题解使用了树状数组（Binary Indexed Tree）来解决问题。树状数组可以在 O(logn) 的时间复杂度内更新元素和计算前缀和。具体思路如下： 1. 在构造函数中，初始化一个大小为 n+1 的树状数组 tree，并将原始数组 nums 中的元素构建到 tree 中。 2. update 方法用于更新 nums[index] 的值为 val。先计算变化量 d，然后从 index+1 开始，不断向上更新 tree 中受影响的节点，每次跳转到当前索引 i 的父节点。 3. pres 方法用于计算前缀和，即计算从索引 1 到索引 i 的元素和。通过从右到左遍历 tree，将途经的节点值累加到结果中。 4. sumRange 方法通过调用 pres 方法计算索引 right+1 和 left 的前缀和，然后相减得到区间 [left, right] 的元素和。

O(logn)

O(n)

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))