LeetCode 307. 区域和检索 - 数组可修改
题目描述
题意分析
实现
NumArray：update(index, val)把一个位置改成新值，sumRange(left, right)返回包含两端的区间和。后续查询必须反映之前的修改。静态前缀和虽然查询快，但单点变化会影响它后面的所有前缀，因此需要能局部维护区间和的数据结构。
解法：树状数组（Fenwick）
核心思路
[!blue]
树状数组将前缀划分成可以快速组合的块。内部下标从 $1$ 开始，定义
lowbit(i) = i & -i，即i的最低置位所代表的二次幂。bit[i]保存以i为右端、长度为lowbit(i)的块和；对应原数组的零基半开区间[i - lowbit(i), i)。查询前缀。
prefix(index)求原数组[0, index]的和，先把右端转换为内部下标i = index + 1。加入bit[i]后，最右边长度为lowbit(i)的一块已经算完，剩下的正好是更短的前缀，因此令i -= lowbit(i)。每次取走的块与前面已取块相邻且不重叠，直到i = 0就覆盖了整个前缀。传播修改。原数组一个位置增加
delta时，所有包含它的块和都应增加同样的量。从内部位置i = index + 1开始，更新bit[i]，再令i += lowbit(i)，跳到下一个包含当前块的更大块。跳过的中间下标对应的块都位于当前块右侧，不包含修改位置，所以不需要更新。重复直到越过数组上界，就维护了这个位置影响的全部块。查询每次去掉二进制最低的一个 $1$；更新则向更大层级的块跳转，两条下标链都只有对数长度。内部不能从下标 $0$ 开始，因为
lowbit(0) = 0，那样更新无法前进。接口给的是新值而不是增量，所以另用
nums保存每个位置的当前值。先计算delta = val - nums[index]，再保存新值并传播delta；bit[index + 1]可能包含一整块，不能把它当作单点旧值。构造时让nums和bit都从全零开始，再逐项调用同一更新过程建立树。最后将区间
[left, right]拆成两个前缀之差：prefix(right) - prefix(left - 1)。当left = 0时，第二项是空前缀，代码返回 $0$，所以首项边界也使用同一公式。
解题步骤
- 初始化零值副本与长度 n+1 的树状数组。
- 逐项更新，完成构造。
- 修改时先算新旧差值，再沿增大的下标链更新。
- 查询两个前缀和并相减。
代码实现
class NumArray {
private int[] nums;
private int[] bit;
public NumArray(int[] nums) {
this.nums = new int[nums.length];
this.bit = 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 delta = val - nums[index];
nums[index] = val;
add(index, delta);
}
public int sumRange(int left, int right) {
return prefix(right) - prefix(left - 1);
}
private void add(int index, int delta) {
int i = index + 1;
while (i < bit.length) {
// 沿包含该位置的块向上更新，下标必须从一开始。
bit[i] += delta;
i += i & -i;
}
}
private int prefix(int index) {
if (index < 0) {
return 0;
}
int res = 0;
int i = index + 1;
while (i > 0) {
// 累加当前末端块，再减去最低位以继续查询剩余前缀。
res += bit[i];
i -= i & -i;
}
return res;
}
}
type NumArray struct {
nums []int
bit []int
}
func Constructor(nums []int) NumArray {
na := NumArray{nums: make([]int, len(nums)), bit: make([]int, len(nums)+1)}
for i := 0; i < len(nums); i++ {
na.Update(i, nums[i])
}
return na
}
func (this *NumArray) Update(index int, val int) {
// 先用保存的旧值求差，再把赋值转为树状数组的增量更新。
delta := val - this.nums[index]
this.nums[index] = val
i := index + 1
for i < len(this.bit) {
// 沿包含该位置的块向上更新，下标必须从一开始。
this.bit[i] += delta
i += i & -i
}
}
func (this *NumArray) SumRange(left int, right int) int {
return this.prefix(right) - this.prefix(left-1)
}
func (this *NumArray) prefix(index int) int {
if index < 0 {
return 0
}
res := 0
i := index + 1
for i > 0 {
// 累加当前末端块，再减去最低位以继续查询剩余前缀。
res += this.bit[i]
i -= i & -i
}
return res
}
复杂度分析
- 时间复杂度：构造 $O(n\log(n+1))$，每次更新和查询 $O(\log(n+1))$。
- 空间复杂度：$O(n+1)$，保存当前值与树状数组。
关键点总结
[!green]
- 赋值接口先转换为增量，不能直接把新值加进去。
- 内部从一下标开始，零不参与更新链。
- 查询拆前缀，更新维护包含该点的各个块。
易错点总结
[!yellow]
- 覆盖旧值之后再算 delta：差值变成零，实际未更新。
- 用 bit[index+1] 当单点旧值：它可能包含一整个块。
- 更新从零下标开始：lowbit(0)=0，循环无法推进。
- 区间减去 prefix(left)：把左端点也扣掉。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 303. 区域和检索 - 数组不可变 | 简单 | 本题增加单点修改，不能仅使用构造一次的静态前缀和。 |
| 308. 二维区域和检索 - 矩阵可修改 | 中等 | 把一维单点更新与区间求和推广到二维矩形查询。 |