LeetCode 308. 二维区域和检索 - 矩阵可修改

2022-01-21 HGNULB 约 16 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 308. 二维区域和检索 - 矩阵可修改

题意分析

设计一个类 NumMatrix，用一个二维矩阵初始化，之后支持两种操作任意次交替调用：update(row, col, val) 把某个格子改成 val，sumRegion(row1, col1, row2, col2) 返回以 (row1, col1) 为左上角、(row2, col2) 为右下角的子矩形内所有元素之和。

这是 307 题从一维推广到二维的版本，考的仍然是两种操作之间的复杂度权衡。先摆两个极端：只存原矩阵时 update 是 $O(1)$ 而 sumRegion 最坏要遍历 $mn$ 个格子；预处理二维前缀和时 sumRegion 是 $O(1)$ 而 update 要重算右下方全部前缀，同样是 $O(mn)$。两者都有一侧退化。

题目明确说明「update 和 sumRegion 会被调用很多次」，这是要求两侧都必须做到对数级的直接信号。「单点修改 + 矩形求和」这个组合指向二维树状数组，能把两个操作都压到 $O(\log m \cdot \log n)$。

接口语义上有一处和 307 相同的陷阱：update 传的是新值而非增量，而树状数组只支持「加一个增量」。所以必须额外维护一份当前值的矩阵副本，用 新值 - 旧值 得到增量。这份副本是接口决定的必需品，不是可选优化。

「矩形和」相比一维的「区间和」多了一层：一维用两个前缀相减，二维必须用容斥，即用四个二维前缀矩形拼出目标矩形。这是本题相对 307 新增的核心考点。

边界：row1 == 0 或 col1 == 0 时容斥会用到「行下标为 -1」或「列下标为 -1」的前缀，必须约定它们返回 0；空矩阵（matrix.length == 0）时 n 无法从 matrix[0] 取出，要单独置 0；row1 == row2 && col1 == col2 时区域退化成单格。

解法：二维树状数组（Fenwick）

核心思路

先明确一维树状数组的不变量，二维只是它的直积。一维里 bit[i] 保存原数组区间 $(i - \mathrm{lowbit}(i),\ i]$ 的和，其中 $\mathrm{lowbit}(i) = i \& (-i)$；查询前缀时不断 i -= lowbit(i) 往回缩，单点加增量时不断 i += lowbit(i) 往上推，两个方向都最多走 $O(\log n)$ 步。

二维的推广方式是把这条规则在行和列上各套一遍。于是不变量变成：bit[r][c] 保存原矩阵中行落在 $(r - \mathrm{lowbit}(r),\ r]$、列落在 $(c - \mathrm{lowbit}(c),\ c]$ 的那个子矩形的元素和。举例：bit[4][6] 管辖第 1 到第 4 行、第 5 到第 6 列围成的 $4 \times 2$ 区域。

有了这条不变量，两个操作就是一维版本的嵌套：

求二维前缀和 sum(row, col)（即左上角固定在 (0,0)、右下角为 (row, col) 的矩形和）：外层从 r = row + 1 开始不断 r -= lowbit(r)，内层从 c = col + 1 开始不断 c -= lowbit(c)，把途经的所有 bit[r][c] 累加。外层每一步选出一段行区间，内层每一步选出一段列区间，两两组合恰好把目标矩形无重不漏地铺满。

单点加增量 add(row, col, delta)：外层 r += lowbit(r)、内层 c += lowbit(c)，把 delta 加到所有管辖这个格子的节点上。同样地，行方向有 $O(\log m)$ 个节点管辖该行，列方向有 $O(\log n)$ 个，笛卡尔积就是 $O(\log m \log n)$ 个待更新节点。

关键在于把「无重不漏」这件事想清楚。一维时，$i \to i - \mathrm{lowbit}(i) \to \cdots \to 0$ 这条链上的节点管辖区间恰好构成 $[1, i]$ 的一个划分。二维时行链和列链各自是一个划分，它们的笛卡尔积就是目标矩形的一个划分——这正是二维树状数组能成立的全部理由，也是它能直接推广到任意维的原因。

最后是容斥。sum(r, c) 只能给出左上角锚定在原点的矩形和，而题目要的是任意矩形。设目标矩形为 $[r_1, r_2] \times [c_1, c_2]$，那么

$S = \mathrm{sum}(r_2, c_2) - \mathrm{sum}(r_1 - 1, c_2) - \mathrm{sum}(r_2, c_1 - 1) + \mathrm{sum}(r_1 - 1, c_1 - 1)$。

直观解释：从大矩形里减掉「上方多出来的横条」和「左边多出来的竖条」，但左上角那块被减了两次，要加回来一次。最后那个 + 号是本题最容易写错的地方，也是与一维版本最大的形式差异。

update 的语义适配和 307 完全一样：delta = val - nums[row][col]，先算增量、再更新副本、最后推进树状数组。构造函数把副本初始化为全 0，再对每个格子调用一次 update，让增量等于原值，从而把整棵二维树建起来。

下标转换同样集中在 add 与 sum 两个私有方法里：树状数组必须 1-based（$\mathrm{lowbit}(0) = 0$ 会让循环卡死），所以 bit 开 $(m+1) \times (n+1)$，进出时做 +1 / -1，对外接口保持题目的 0-based。

解题步骤

成员变量设计：nums 是当前值的矩阵副本，bit 是 $(m+1) \times (n+1)$ 的二维树状数组，另存 m、n。为什么必须有 nums 副本——接口给新值而结构只吃增量，没有副本算不出 delta；为什么 bit 两个维度都多开一位——1-based 下标要求行 0 和列 0 空置。

构造函数先算出 m、n 并处理空矩阵：m == 0 时 n 直接置 0。为什么必须判——否则 matrix[0].length 会越界。

nums 初始化为全 0，再对每个格子调用 update(r, c, matrix[r][c])：为什么初值必须是 0——这样 delta = matrix[r][c] - 0 恰好等于原值，一次 update 完成「从无到有插入」；若把副本直接填成原矩阵，delta 全为 0，bit 保持全零，所有查询返回 0。

add(row, col, delta) 用双重 for 向右下推：外层 r 从 row + 1 起、条件 r <= m、步进 r += r & -r；内层 c 同理。为什么是「加 lowbit」——被更新的格子会影响所有管辖它的节点，这些节点的下标正由不断加 lowbit 生成；为什么内层每次都要从 col + 1 重新起步——行链上的每个节点都需要在列方向独立走一遍完整的链。

sum(row, col) 先判 row < 0 || col < 0 返回 0：为什么必须判——容斥会传入 row1 - 1 和 col1 - 1，当 row1 或 col1 为 0 时这些参数是 -1，语义是「空矩形」，必须返回 0 而不是越界或误算。

sum 用双重 for 向左上缩：外层 r 从 row + 1 起、条件 r > 0、步进 r -= r & -r；内层同理，累加 bit[r][c]。为什么是「减 lowbit」——bit[r][c] 已经覆盖了行区间 $(r - \mathrm{lowbit}(r), r]$，剩余部分的右边界正是 r - lowbit(r)。

update(row, col, val) 严格按「算增量 → 更新副本 → 推进树」三步：为什么顺序不可调换——delta 依赖旧值，先覆盖副本会让 delta 恒为 0。

sumRegion 按容斥公式组合四次 sum：符号是「右下 − 上 − 左 + 左上」。为什么最后要加回来——左上角那块区域在减去上方横条和左侧竖条时被扣了两次，必须补一次。

以 matrix = [[3, 0, 1], [5, 6, 3]] 走一遍（$m = 2$、$n = 3$，bit 是 $3 \times 4$）。

构造阶段。副本初始为 [[0,0,0],[0,0,0]]，bit 全零。

update(0, 0, 3)：delta = 3。add(0, 0, 3) 的外层 r 从 1 开始：r = 1 时内层 c 从 1 走到 2（lowbit(1)=1）再到 4（lowbit(2)=2，超过 n = 3 停），所以 bit[1][1] += 3、bit[1][2] += 3；r += lowbit(1) = 1 变成 2，内层同样走 c = 1, 2，得 bit[2][1] += 3、bit[2][2] += 3；r += lowbit(2) = 2 变成 4 超过 m = 2，停止。

update(0, 1, 0)：delta = 0，各节点加 0，bit 不变，副本 [0][1] 记为 0。

update(0, 2, 1)：delta = 1。列起点 c = 3，链是 3 → 4（超界停），所以只有 bit[r][3]；行链是 1 → 2。结果 bit[1][3] += 1、bit[2][3] += 1。

update(1, 0, 5)：delta = 5。行起点 r = 2，链是 2 → 4（超界停），只有 bit[2][*]；列链 1 → 2。结果 bit[2][1] += 5 得 8、bit[2][2] += 5 得 8。

update(1, 1, 6)：delta = 6。行链只有 r = 2；列起点 c = 2，链是 2 → 4（超界停），只有 c = 2。结果 bit[2][2] += 6 得 14。

update(1, 2, 3)：delta = 3。行链 r = 2；列链 c = 3。结果 bit[2][3] += 3 得 4。

最终 bit（忽略第 0 行第 0 列）为：bit[1] = [_, 3, 3, 1]，bit[2] = [_, 8, 14, 4]。

核对不变量抽查两个：bit[1][2] 管辖行 $(0,1]$、列 $(0,2]$，即 matrix[0][0] + matrix[0][1] = 3 + 0 = 3，✓；bit[2][2] 管辖行 $(0,2]$、列 $(0,2]$，即 $3+0+5+6 = 14$，✓。

sumRegion(0, 0, 1, 2)（整个矩阵，期望 $3+0+1+5+6+3 = 18$）：容斥四项是 sum(1,2) - sum(-1,2) - sum(1,-1) + sum(-1,-1)。后三项因为有负下标全部返回 0。sum(1, 2)：外层 r = 2，内层 c = 3 累加 bit[2][3] = 4，c -= lowbit(3) = 1 变成 2 累加 bit[2][2] = 14，c -= 2 变成 0 停；小计 18。r -= lowbit(2) = 2 变成 0，外层停。结果 18，正确。

sumRegion(1, 1, 1, 2)（第 1 行的第 1、2 列，期望 $6 + 3 = 9$）：容斥是 sum(1,2) - sum(0,2) - sum(1,0) + sum(0,0)。sum(1,2) = 18。sum(0,2)：r = 1，c = 3 累加 bit[1][3] = 1，c = 2 累加 bit[1][2] = 3，c = 0 停；小计 4；r -= 1 变 0 停。得 4（即第 0 行前三个数 $3+0+1$，✓）。sum(1,0)：r = 2，c = 1 累加 bit[2][1] = 8，c = 0 停；r = 0 停。得 8（即第 0、1 行的第 0 列 $3+5$，✓）。sum(0,0)：r = 1、c = 1 累加 bit[1][1] = 3。得 3。合计 $18 - 4 - 8 + 3 = 9$，正确。注意最后那个 +3：matrix[0][0] 在减去 sum(0,2) 和 sum(1,0) 时被扣了两次，不加回来结果会是 6，少了 3。

update(1, 1, 10) 之后再查一次：delta = 10 - 6 = 4，行链 r = 2、列链 c = 2，只改 bit[2][2]，从 14 变成 18。再算 sumRegion(1, 1, 1, 2)：sum(1,2) 变成 $4 + 18 = 22$，sum(0,2) 仍是 4，sum(1,0) 仍是 8，sum(0,0) 仍是 3，结果 $22 - 4 - 8 + 3 = 13$，即 $10 + 3$，正确。整次更新只碰了 1 个节点，正是二维树状数组把 $O(mn)$ 更新压到对数级的体现。

代码实现

// 用 bit[r][c] 维护二维前缀增量，update 用差值更新。
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;
    }
}

// 用 bit[r][c] 维护二维前缀增量，update 用差值更新。
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 \log n)$，update 与 sumRegion 均为 $O(\log m \cdot \log n)$。凭什么：add 的外层每次 r += lowbit(r) 至多执行 $O(\log m)$ 次，内层每次 c += lowbit(c) 至多 $O(\log n)$ 次，嵌套后是两者之积；sum 的两层循环各自消掉下标二进制里的一个 1，同样是 $O(\log m \log n)$；sumRegion 调用四次 sum，常数 4 不改变量级；构造函数对 $mn$ 个格子各调用一次 update。

空间复杂度：$O(mn)$。bit 是 $(m+1) \times (n+1)$ 的二维数组，nums 副本是 $m \times n$，两者同阶；所有操作都是迭代实现。二维线段树也可做到线性量级空间，但实现与常数通常更大，不能把其空间一概写成 $O(mn \log m \log n)$。

关键点总结

高维树状数组就是一维规则在每个维度上各套一遍：bit 的下标链在每一维独立地加/减 lowbit，管辖区域是各维区间的笛卡尔积。理解了「行链和列链各是一个划分，直积仍是划分」，就能把它推广到任意维而不必死记代码。

二维前缀只能给出锚定原点的矩形，任意矩形必须靠容斥：右下减上边减左边加左上。加回左上角这一项是最高频的遗漏，写公式时可以画个田字格数一遍每块被加减了几次来自检。

树状数组必须 1-based，因为 $\mathrm{lowbit}(0) = 0$ 会让两个方向的循环都无法推进。把 +1 / -1 的转换封装在私有方法内部，对外维持题目的 0-based 接口，是清晰的分层。

接口给「设为新值」而底层只支持「加增量」时，必须维护当前值副本来做差。这个适配模式在 307、二维版本、以及所有基于差分的结构里都一样。

前缀查询要为「下标为 -1」的空前缀显式返回 0，这是容斥公式能统一处理边界矩形的前提，不能靠数组越界的偶然行为。

面试视角：这题几乎不会独立出现，通常是 307 的追问。标准答法是先复述一维树状数组的不变量，再说明「每维各套一遍」的推广方式，最后重点讲容斥公式的推导。被问「为什么不用二维线段树」时要能答出：本题只需单点改 + 区间和这类可减信息，二维树状数组代码不到二十行且常数小；二维线段树只有在需要区间修改或区间最值时才值得。

面试视角：另一个常见追问是「矩阵很大但非零元素很少怎么办」。要能答出改用哈希表存 bit 做稀疏化，或者按行分块，避免 $O(mn)$ 的稠密数组。

易错点总结

容斥漏掉最后的加项，写成 sum(r2,c2) - sum(r1-1,c2) - sum(r2,c1-1)：用例 matrix = [[3,0,1],[5,6,3]]、sumRegion(1,1,1,2)，会算成 $18-4-8 = 6$ 而正确答案是 9，左上角的 matrix[0][0] = 3 被减了两次。

容斥的加项写成减号：同一用例会得到 $18-4-8-3 = 3$，偏差更大；符号必须是「减、减、加」。

容斥用 row1 而不是 row1 - 1：用例 sumRegion(1,1,1,2)，用 sum(row1, c2) 会把第 1 行本身也扣掉，结果偏小；前缀是闭区间，扣的必须是 row1 - 1。

sum 没有处理负下标：用例 sumRegion(0,0,1,2) 会调用 sum(-1, 2)，若不提前返回 0，r = -1 + 1 = 0 时循环条件 r > 0 不成立而返回 0 尚能侥幸；但若把循环条件误写成 r >= 0，lowbit(0) = 0 会让 r 永远停在 0，陷入死循环。

update 里直接 add(row, col, val) 把新值当增量：用例先 update(1,1,6) 再 update(1,1,10)，正确结果是该格变成 10，这种写法会变成 16，sumRegion(1,1,1,1) 返回 16。

update 里先写副本再算 delta：用例 update(1,1,10) 当旧值是 6 时，delta 变成 0，bit 完全不动，查询仍返回旧的 6。

构造函数把 nums 直接指向传入的 matrix：用例 matrix = [[3,0,1],[5,6,3]]，每次 delta = matrix[r][c] - matrix[r][c] = 0，bit 全零，所有 sumRegion 返回 0。

add 的内层循环没有在每一轮外层重新初始化 c：用例 update(0,0,3)，若把 c 提到外层之前只初始化一次，第二轮外层（r = 2）时 c 已经是超界值，bit[2][*] 一个都不会被更新，后续包含第 1 行的查询全部偏小。

add 与 sum 的跳跃方向写反：用例 matrix = [[3]]，add 若写成 r -= r & -r 会从 r = 1 直接跳到 0 退出，bit 全零；sum 若写成 r += r & -r 则会越界或死循环。

bit 只开 m × n 而非 (m+1) × (n+1)：用例 matrix = [[3]]（$m = n = 1$），add(0,0,3) 时 r = 1 会访问 bit[1][1] 直接越界。

循环上界写成 r < m 而不是 r <= m：用例 matrix = [[3],[5]]（$m = 2$），add(1, 0, 5) 时 r = 2 不满足 r < 2，这个格子的增量根本没被写进去，sumRegion(0,0,1,0) 返回 3 而正确答案是 8。

空矩阵未处理：用例 matrix = []，构造函数取 matrix[0].length 直接越界（Go 版 panic）。

lowbit 写成 r & (r - 1)：用例任意，6 & 5 = 4 而 lowbit(6) = 2，这是「消掉最低位 1」而非「取出最低位 1」，两条链的走法全错。

相似题目

题目	难度	考察点
307. 区域和检索 - 数组可修改	中等	本题的一维原型，先吃透单维 lowbit 链再推广，容斥退化为两个前缀相减
303. 区域和检索 - 数组不可变	简单	没有修改操作，纯前缀和即可，用来对照理解修改需求如何逼出树状数组
304. 二维区域和检索 - 矩阵不可变	中等	只需二维前缀和数组，是本题容斥公式的最小载体，不涉及 lowbit
315. 计算右侧小于当前元素的个数	困难	树状数组建在值域上做计数而非求和，需要先离散化
327. 区间和的个数	困难	前缀和配合值域树状数组统计满足条件的历史前缀个数，考察问题到计数的转化
493. 翻转对	困难	同为值域计数但比较条件带系数，离散化时要把 $2 \times nums[i]$ 一并放进值域
850. 矩形面积 II	困难	二维聚合但需要扫描线加线段树，说明何时二维树状数组不再够用