区域和检索 - 数组可修改

难度: Medium

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

其中一类查询要求更新数组 nums 下标对应的值
另一类查询要求返回数组 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 * 10⁴
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
调用 update 和 sumRange 方法次数不大于 3 * 10⁴

Submission

运行时间: 612 ms

内存: 33.6 MB

class NumArray:

    def __init__(self, nums: List[int]):
        n = len(nums)
        tree = [0] * (n+1)
        for i,x in enumerate(nums,1):
            tree[i] += x
            nxt = i+(i&-i)
            if nxt <= n:
                tree[nxt] += tree[i]
        self.nums = nums
        self.tree = tree


    def update(self, index: int, val: int) -> None:
        d = val - self.nums[index]
        self.nums[index] = val
        i = index + 1
        while i < len(self.tree):
            self.tree[i] += d
            i += i&-i

    def pres(self,i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i&-i
        return s

    def sumRange(self, left: int, right: int) -> int:
        return self.pres(right+1) - self.pres(left)



# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)

Explain

这个题解使用了树状数组（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)

class NumArray:

    def __init__(self, nums: List[int]):
        n = len(nums)
        # 初始化大小为 n+1 的树状数组 tree
        tree = [0] * (n+1)
        # 将原始数组 nums 中的元素构建到 tree 中
        for i,x in enumerate(nums,1):
            tree[i] += x
            nxt = i+(i&-i)
            if nxt <= n:
                tree[nxt] += tree[i]
        self.nums = nums
        self.tree = tree


    def update(self, index: int, val: int) -> None:
        # 计算变化量 d
        d = val - self.nums[index]
        self.nums[index] = val
        i = index + 1
        # 从 index+1 开始向上更新 tree 中受影响的节点
        while i < len(self.tree):
            self.tree[i] += d
            i += i&-i

    def pres(self,i):
        s = 0
        # 从右到左遍历 tree，将途经的节点值累加到结果中
        while i:
            s += self.tree[i]
            i -= i&-i
        return s

    def sumRange(self, left: int, right: int) -> int:
        # 计算索引 right+1 和 left 的前缀和，然后相减得到区间 [left, right] 的元素和
        return self.pres(right+1) - self.pres(left)

Explore

树状数组的索引从 1 开始，这样做是为了简化父节点和子节点之间的索引计算。如果数组从 0 开始，则每次进行 i += i & -i 和 i -= i & -i 操作时需要额外的条件判断和调整，使得实现更加复杂。使用从 1 开始的索引可以直接使用 i & -i 来快速定位到影响的区间，从而保持代码的简洁性和操作的高效性。

变化量 d 是指更新操作后元素的值与更新前的值之间的差额。具体计算方式是 d = val - self.nums[index]，其中 val 是更新后的新值，self.nums[index] 是更新前数组中该位置的旧值。这个差值 d 表示了该索引位置增加或减少的量，这个变化量将用于调整树状数组中的相关节点，以保证数组的前缀和正确反映数组的当前状态。

在树状数组中，i += i & -i 是一个关键步骤，用于在更新操作中定位到下一个需要更新的索引。这里的 i & -i 计算得到的是 i 的二进制表示中最低位的 1 对应的值，这个值表示当前索引所覆盖的区间长度。通过加上这个值，索引 i 跳转到下一个需要更新的位置，这样可以保证所有包含原始数组中 index 位置的区间都会被更新。这是一个高效的跳转方法，确保了树状数组的更新操作的时间复杂度为 O(log n)。

这是因为树状数组的设计是从索引 1 开始的，并且是闭区间的计算模式，即计算到当前索引为止的所有元素的和。因此，要获取区间[left, right]的和，我们需要计算从开始到right的所有元素的和，减去从开始到left-1的所有元素的和。为了方便直接使用前缀和函数 pres，我们计算pres(right+1)（即从1到right的和）和pres(left)（即从1到left-1的和），然后将两者相减，得到区间[left, right]的元素和。