LeetCode 308. 二维区域和检索 - 矩阵可修改
题目描述
题意分析
维护一个会被反复修改的二维矩阵：
update(row, col, val)将单个格子设为新值，sumRegion(row1, col1, row2, col2)查询包含上下左右边界的矩形和。查询需要反映此前的所有更新。
解法：二维树状数组（Fenwick）
核心思路
[!blue]
一维树状数组保存若干区间块的和，二维版本则把行块与列块组合成矩形块。内部行列下标都从 $1$ 开始，
lowbit(x) = x & -x。bit[r][c]对应原矩阵的零基半开区域[r - lowbit(r), r) × [c - lowbit(c), c)，即高为lowbit(r)、宽为lowbit(c)的矩形和。单点更新：先用
nums[row][col]保存的旧值计算delta = val - old，再保存新值。内部从(row + 1, col + 1)出发，行下标不断加lowbit(r)，列下标不断加lowbit(c)，分别访问包含当前行、当前列的所有更大块。把两条链嵌套起来，就恰好覆盖所有包含这个格子的矩形块，对它们各加一次delta。左上前缀查询：
sum(row, col)表示[0, row] × [0, col]的和。内部行下标不断减lowbit(r)，把行范围拆成互不重叠的块；对每个行块，列下标也不断减lowbit(c)，把列范围拆开。两组分段的所有组合正好铺满查询前缀矩形，既不遗漏，也不重复。更新和查询中，每进入一个新的行块，列下标都必须重新从
col + 1出发。因为每个行块都需要完整遍历同一条列链，不能沿用前一行循环已经耗尽的列下标。任意矩形查询：先取
sum(row2, col2)，减去row1上方的前缀sum(row1 - 1, col2)，再减去col1左侧的前缀sum(row2, col1 - 1)。左上角同时属于这两块，被多减了一次，所以最后加回sum(row1 - 1, col1 - 1)。某个下标为负时表示空前缀，统一返回 $0$，从首行或首列开始的区域无需特判。构造时创建全零的当前值副本和树状数组，再逐格调用更新。每次把该位置从 $0$ 改为输入值，也就把相同增量加入所有相关矩形块，建立好后续查询需要的状态。
解题步骤
- 初始化零值副本和两维各多一位的树状数组。
- 逐格更新完成构造。
- 单点赋值先计算 delta，再沿两维更新链传播。
- 区域查询组合四次前缀，符号为加、减、减、加。
代码实现
class NumMatrix {
private int[][] nums;
private int[][] bit;
private int m;
private int n;
public NumMatrix(int[][] matrix) {
m = matrix.length;
if (m == 0) {
n = 0;
} else {
n = matrix[0].length;
}
nums = new int[m][n];
bit = new int[m + 1][n + 1];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
update(r, c, matrix[r][c]);
}
}
}
public void update(int row, int col, int val) {
// 先计算新旧差值，后续更新只传播这个增量。
int delta = val - nums[row][col];
nums[row][col] = val;
add(row, col, delta);
}
public int sumRegion(int row1, int col1, int row2, int col2) {
// 容斥扣掉上方和左侧，再加回重复扣除的左上区域。
return sum(row2, col2)
- sum(row1 - 1, col2)
- sum(row2, col1 - 1)
+ sum(row1 - 1, col1 - 1);
}
private void add(int row, int col, int delta) {
for (int r = row + 1; r <= m; r += r & -r) {
// 每个行链节点都要从原列位置重新遍历整条列链。
for (int c = col + 1; c <= n; c += c & -c) {
bit[r][c] += delta;
}
}
}
private int sum(int row, int col) {
if (row < 0 || col < 0) {
return 0;
}
int res = 0;
for (int r = row + 1; r > 0; r -= r & -r) {
for (int c = col + 1; c > 0; c -= c & -c) {
res += bit[r][c];
}
}
return res;
}
}
type NumMatrix struct {
nums [][]int
bit [][]int
m int
n int
}
func Constructor(matrix [][]int) NumMatrix {
m := len(matrix)
n := 0
if m > 0 {
n = len(matrix[0])
}
nums := make([][]int, m)
for i := 0; i < m; i++ {
nums[i] = make([]int, n)
}
bit := make([][]int, m+1)
for i := 0; i <= m; i++ {
bit[i] = make([]int, n+1)
}
nm := NumMatrix{nums: nums, bit: bit, m: m, n: n}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
nm.Update(r, c, matrix[r][c])
}
}
return nm
}
func (this *NumMatrix) Update(row int, col int, val int) {
// 先计算新旧差值，后续更新只传播这个增量。
delta := val - this.nums[row][col]
this.nums[row][col] = val
for r := row + 1; r <= this.m; r += r & -r {
// 每个行链节点都要从原列位置重新遍历整条列链。
for c := col + 1; c <= this.n; c += c & -c {
this.bit[r][c] += delta
}
}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
// 容斥扣掉上方和左侧，再加回重复扣除的左上区域。
return this.sum(row2, col2) - this.sum(row1-1, col2) - this.sum(row2, col1-1) + this.sum(row1-1, col1-1)
}
func (this *NumMatrix) sum(row int, col int) int {
if row < 0 || col < 0 {
return 0
}
res := 0
for r := row + 1; r > 0; r -= r & -r {
for c := col + 1; c > 0; c -= c & -c {
res += this.bit[r][c]
}
}
return res
}
复杂度分析
- 时间复杂度：构造 $O(mn\log(m+1)\log(n+1))$，单次更新和区域查询 $O(\log(m+1)\log(n+1))$。
- 空间复杂度：$O((m+1)(n+1))$，保存当前值和包含哨兵行列的树状数组。
关键点总结
[!green]
- 两维下标链独立嵌套，列循环每次重新起步。
- 更新先保留旧值求差，再写入新值。
- 容斥最后加回左上部分，避免重复扣减。
易错点总结
[!yellow]
- 漏掉容斥加回项：左上交叠区域被扣两次。
- 内层列下标只初始化一次：后续行链节点得不到更新。
- 下标未转换为从一开始：更新可能停在零而无法前进。
- 把新值直接当增量：重复赋值会不断增加数值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 304. 二维区域和检索 - 矩阵不可变 | 中等 | 本题增加单点更新，需要二维树状数组等动态结构替代静态前缀矩阵。 |
| 307. 区域和检索 - 数组可修改 | 中等 | 同样支持更新与区间和，本题把树状数组的下标跳转扩展到两个维度。 |