0307. Range Sum Query - Mutable
===============================
题目信息
--------
:题号: 0307
:难度: Medium
:主题: 数组、可变对象、单点更新、区间和
:原题: `LeetCode 0307 `_
:重点: 更新会改变后续查询状态、区间包含两个端点、同一对象支持交错调用
题目重述
--------
实现 ``NumArray`` 类。构造函数接收整数数组 ``nums``;``update(index, val)`` 把下标 ``index`` 的元素替换为 ``val``;``sumRange(left, right)`` 返回当前数组中闭区间 ``[left, right]`` 的元素总和。
数组长度位于 ``[1, 3 * 10^4]``,初始元素及更新值均位于 ``[-100, 100]``。更新下标始终有效,查询满足 ``0 <= left <= right < nums.length``。``update`` 与 ``sumRange`` 的总调用次数不超过 ``3 * 10^4``;每次更新都必须影响之后在同一对象上执行的查询。
自建示例
--------
查询与更新交错发生:
.. code-block:: text
输入:NumArray([4, -1, 6])
sumRange(0, 2)
update(1, 5)
sumRange(0, 2)
sumRange(1, 1)
输出:9
null
15
5
解释:更新把数组从 [4,-1,6] 改为 [4,5,6];后两次查询都必须读取更新后的值。
用树状数组同时维护更新与查询
------------------------------
不可变版本的前缀和不再适用:修改下标 ``index`` 后,所有右侧前缀都要重新计算。这里使用树状数组(Fenwick tree)保存若干个“低位区间和”。它支持两种互为配合的操作:把某个位置增加一个差值,以及求从下标 0 到某位置的前缀和;两者都只沿树状数组的一条路径移动,时间为 ``O(log n)``。
对象中同时保存当前数组 ``nums``。执行 ``update(index, val)`` 时,先计算 ``delta = val - nums[index]``,把数组中的旧值改成新值,再把这个差值加入树状数组。这样后续的区间查询读到的就是更新后的状态。闭区间和仍由两个前缀和相减得到。
C++ 实现
--------
.. code-block:: cpp
class NumArray {
int n;
std::vector nums;
std::vector tree;
void add(int index, long long delta) {
for (int i = index + 1; i <= n; i += i & -i) {
tree[i] += delta;
}
}
long long prefixSum(int index) const {
long long result = 0;
for (int i = index + 1; i > 0; i -= i & -i) {
result += tree[i];
}
return result;
}
public:
NumArray(std::vector& values)
: n(static_cast(values.size())),
nums(values), tree(n + 1, 0) {
for (int i = 0; i < n; ++i) {
add(i, nums[i]);
}
}
void update(int index, int val) {
long long delta = static_cast(val) - nums[index];
nums[index] = val;
add(index, delta);
}
int sumRange(int left, int right) const {
long long result = prefixSum(right);
if (left > 0) result -= prefixSum(left - 1);
return static_cast(result);
}
};
代码分析
--------
树状数组使用一位偏移的内部下标,避免了原数组下标 0 在 ``i & -i`` 中没有有效低位的问题。更新数组副本和树状数组必须同步,否则同一次对象上的交错调用会产生错误结果。构造时间为 ``O(n log n)``,每次更新和区间查询均为 ``O(log n)``,额外空间为 ``O(n)``。