查询的优化实战)
1. 子矩阵求和为什么值得专门学一下
先聊个实际场景。你手里有一张数字表，比如一张灰度图、一份销售数据矩阵，或者游戏里的地形数值表，想快速知道某个矩形区域内所有数字的总和。最直觉的做法是双重循环挨个加，一次查询就是 O(n*m) 的时间，如果查询次数多、矩阵又大，很快就会被卡死。
我第一次写这类题时也被这个 O(n*m) 的复杂度坑过。当时要做热力图区域统计，一个 2000×2000 的矩阵，查一万个子区域，循环加法的耗时直接跑到几秒开外，调到后面整个人都麻了。后来换成了二维前缀和预处理，查询直接变成 O(1)，同样的数据量跑完只用了原来零头的时间。
这里的核心思路就是"用空间换时间"。二维前缀和本质上是一张和原始矩阵同尺寸的"累计和表"，每个位置存的是从左上角 (1,1) 到当前点 (i,j) 这个矩形区域里所有数字的总和。有了这张表，任意子矩阵的和都可以通过四个查表值的加减组合算出来，不再需要遍历矩阵里的每一个元素。
这个技巧不止在算法题里有用。图像处理里做快速区域亮度统计、数据分析里做时间窗口聚合、游戏开发里做地图网格覆盖计算，凡是"频繁求矩形区域总和"的场景，基本都是这套东西在打底。经典题目 796. 子矩阵的和 就是把这个思路练熟的最佳模板，搞懂它之后，你会发现很多看起来很吓人的题，底层其实都是前缀和变种。
2. 二维前缀和的核心原理拆解
2.1 从一维前缀和推过去
先复习一维前缀和。给你一个数组 a[1] 到 a[n]，定义 prefix[i] = a[1] + a[2] + ... + a[i]。那么区间 [l, r] 的和就是 prefix[r] - prefix[l-1]。预计算 O(n)，之后每次查询 O(1)，原理很简单：把前 r 项的总和减去前 l-1 项的总和，中间那一段自然就剩下了。
二维前缀和就是把这个思想升级一个维度。定义 S[i][j] = 从 (1,1) 到 (i,j) 这个矩形区域所有元素之和。我们想知道左上角坐标为 (x1, y1)、右下角坐标为 (x2, y2) 的任意子矩阵的和，能不能只靠 S 表里的几个值算出来呢？答案是可以。
如果你把 S[x2][y2] 想象成"从起点到右下角"的全部区域，那它既包含了我们想要的子矩阵，也包含了子矩阵上方、左方、以及左上角那一大块。想要精确地留下中间这一块，就得用容斥的思想：先减去上方部分，再减去左方部分，但左上角那块被减了两次，需要加回来一次。
写成公式就是：
子矩阵和 = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]
这个公式是整个二维前缀和的灵魂。你不需要强行背它，想清楚"减多了要加回来"就永远不会乱。
提示：为了不单独处理边界，通常让矩阵坐标从 1 开始计数，把 0 行 0 列全部留成 0。这样 x1-1 或 y1-1 为 0 时，对应的 S 值就是 0，公式依旧成立，代码不用写一堆 if 判断。
2.2 预处理表怎么算出来
有了公式之后，关键问题变成：S[i][j] 这张表本身怎么高效生成？如果每个点都重新累加，复杂度又回到 O(n*m) 每格，那预处理就失去意义了。正确的做法是利用递推关系。
S[i][j] 表示从 (1,1) 到 (i,j) 的矩形和。它其实可以看成三部分相加：
- 上面的矩形：从 (1,1) 到 (i-1,j)，即 S[i-1][j]
- 左边的矩形：从 (1,1) 到 (i,j-1)，即 S[i][j-1]
- 当前位置的值 a[i][j]
但 S[i-1][j] 和 S[i][j-1] 有重叠部分，就是左上角从 (1,1) 到 (i-1,j-1) 的那一块，也就是 S[i-1][j-1]，它被加了两次，要减掉一次。
所以递推公式是：
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j]
整个过程只需要从左到右、从上到下地扫一遍矩阵，每个位置做三次加减运算，时间复杂度 O(n*m)。这张表建好之后，所有子矩阵查询就都是 O(1) 了。
3. 经典模板题 796 的完整解析
3.1 题目到底在问什么
题目"796. 子矩阵的和"很直接：给定一个 n 行 m 列的整数矩阵，再给你 q 次询问，每次问一个矩形区域的元素和，矩形用左上角坐标 (x1, y1) 和右下角坐标 (x2, y2) 标定。n、m 可以上千，q 也可能上千甚至上万，如果每次暴力遍历，最坏情况是 O(q * n * m)，直接超时。
这类题就是专门为二维前缀和准备的。先读入矩阵，构建前缀和表，然后每次询问用容斥公式四步算出结果，复杂度从 O(q * n * m) 降到 O(n*m + q)，肉眼可见的质变。
3.2 带注释的参考代码
下面这份是 C++ 的模板写法，也是这套题最标准的打开方式。
#include <iostream> using namespace std; const int N = 1010; int a[N][N]; // 原始矩阵 int s[N][N]; // 二维前缀和表 int main() { int n, m, q; cin >> n >> m >> q; // 读入矩阵，坐标从 1 开始，方便处理边界 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; // 构建二维前缀和表 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]; // 处理 q 次询问 while (q--) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; // 容斥求子矩阵和 cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] << endl; } return 0; }这份代码里最值得注意的就是下标从 1 开始这个约定。别小看这个习惯，它让"差值为 0 的边界"自动变成了 0 值，省掉了一整类边界条件判断，写起来清爽，也不容易出错。
3.3 Python 版本参考
Python 写这个题也很方便，注意一下读入方式就行。
n, m, q = map(int, input().split()) # 多开一行一列，所有下标从 1 开始 a = [[0] * (m + 1) for _ in range(n + 1)] s = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): row = list(map(int, input().split())) for j in range(1, m + 1): a[i][j] = row[j - 1] s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j] for _ in range(q): x1, y1, x2, y2 = map(int, input().split()) result = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] print(result)这里我把读入和构建前缀和放在同一个循环里完成了，因为 s[i][j] 只依赖上一行、左一列和左上角的值，这三者都已经被算出来了。写在一遍里既省代码，又不会错乱。
4. 手把手推导一次查询过程
光看代码可能还不够，我拿一个实际例子走一遍全过程。假设原始矩阵是：
1 2 3 4 5 6 7 8 9坐标从 1 开始，即 a[1][1]=1，a[1][2]=2，a[1][3]=3，a[2][1]=4，以此类推。
构建前缀和表。先算第一行：
- s[1][1] = 0 + 0 - 0 + 1 = 1
- s[1][2] = 1 + 0 - 0 + 2 = 3
- s[1][3] = 3 + 0 - 0 + 3 = 6
第二行：
- s[2][1] = 0 + 1 - 0 + 4 = 5
- s[2][2] = s[1][2] + s[2][1] - s[1][1] + 5 = 3 + 5 - 1 + 5 = 12
- s[2][3] = s[1][3] + s[2][2] - s[1][2] + 6 = 6 + 12 - 3 + 6 = 21
第三行：
- s[3][1] = 0 + 5 - 0 + 7 = 12
- s[3][2] = s[2][2] + s[3][1] - s[2][1] + 8 = 12 + 12 - 5 + 8 = 27
- s[3][3] = s[2][3] + s[3][2] - s[2][2] + 9 = 21 + 27 - 12 + 9 = 45
所以前缀和表是：
1 3 6 5 12 21 12 27 45现在来问一个子矩阵：左上角 (2,2)，右下角 (3,3)，也就是数字 5、6、8、9 这个 2×2 的方块。肉眼算一下：5 + 6 + 8 + 9 = 28。
代入公式：
- s[3][3] = 45
- s[1][3] = 6
- s[3][1] = 12
- s[1][1] = 1
结果 = 45 - 6 - 12 + 1 = 28。
完全正确。你可以从这个例子里看到，查询过程真的只有四次查表、三次减法一次加法，完全不需要碰矩阵里任何一个原始元素。这就是 O(1) 查询的含义。
5. 从模板题到实战场景的迁移
5.1 图像的局部特征统计
图像处理里这种需求非常常见。比如你要做人脸区域的亮度均值分析，或者做细胞图像里某个矩形区域的像素强度累加，这张图本质上就是一个巨大的矩阵，每个像素的灰度值就是矩阵元素。先对整张图构建二维前缀和，之后你无论框出多少个不同区域，都能瞬间得到区域总和，再做除法就是均值。批量检测几百个候选区域时，这个速度提升完全能感受到。
5.2 正方形子矩阵的延伸技巧
热词里提到了"正方形子矩阵"，这其实是二维前缀和最常见的延伸考点。题目要求"求所有边长为 k 的正方形子矩阵的和"或者"求最大全 1 正方形面积"时，前缀和依然是底层工具。前者只需要枚举每个可能的左上角坐标，用 O(1) 查表拿区域和做统计；后者是配合二分答案或者动态规划来做，但验证某个 k×k 区域是否满足条件时，仍然离不开区域和的快速查询。
我印象很深的是做过一道地图题，要求在网格地图里找出所有尺寸为 L×L 的平坦区域（区域内高度差不超过某个阈值）。暴力做法是每个区域都遍历一遍，复杂度 L² 乘以区域数，几乎没法跑。后来我先用前缀和快速算区域总和、区域平方和，然后通过方差公式判断平坦程度，整个地图几分钟就能全部筛完。这就是同一种思维在不同载体上的复用。
5.3 可能踩到的几个坑
第一，数组维度不够。有些同学在刷题平台上报"数组越界"，多半是只开了 n×m 却用了 n+1 行 m+1 列的下标。前缀和的 0 行 0 列是必须存在的，不然递推公式会访问到未定义的值。现场写代码时，建议直接把数组维度定义为 N+1、M+1，后面就不用提心吊胆。
第二，坐标输入顺序搞错。有些题目给的是 (x1, y1, x2, y2)，有些给的是 (x1, y1, x2, y2) 但行列顺序反着来。拿到题先看几遍样例，确认清楚哪个是行、哪个是列，再代入公式。我就见过有人把 x 和 y 反着用，样例过了但提交全错，后来才发现是读入顺序理解反了。
第三，数据范围很大时用 int 会爆。一千乘一千的矩阵，如果每个元素是 10 的 9 次方级别，前缀和早就超过 int 上限了。C++ 里用 long long，Python 虽然随便写，但也要注意性能，尽量用 sys.stdin 的批量读入方式，避免逐行 input 拖慢速度。
6. 新手最容易犯的错和排查思路
6.1 边界条件导致答案错误
我最初写二维前缀和时，最喜欢犯的错就是查询时忘了把左上角从 (x1, y1) 对应到公式里的 (x1-1, y1-1)。总想着"我求的就是从 x1 开始，那减 x1 行不行"？还真不行。你要减的是"子矩阵上方和左方的所有区域"，而上方区域的右边界是整个矩阵的右边界，左方区域的下边界是整个矩阵的下边界，不是子矩阵边上那一两根线。
如果发现结果莫名其妙偏小或者偏大，先检查公式里的两个减法和一个加法是不是抄对了。我习惯在草稿纸上画一个矩形，把 S[x2][y2]、S[x1-1][y2]、S[x2][y1-1]、S[x1-1][y1-1] 四个区域分别涂色，用颜色的重叠关系去验证公式，比干瞪眼调试快得多。
6.2 预处理写错导致全盘皆输
递推公式 S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j] 也是不少人写错的地方。有人会把中间的减号写成加号，有人会把 a[i][j] 的位置搞混。这里有个自检技巧：算完前缀和后，手动验证几个位置，比如 s[1][1] 应该等于 a[1][1]，s[1][2] 应该等于 a[1][1] + a[1][2]，s[2][1] 应该等于 a[1][1] + a[2][1]。只要这几个基础位置对得上，递推公式基本没问题。
6.3 常见问题速查
| 问题表现 | 可能原因 | 排查方向 |
|---|---|---|
| 小样例通过，大数据超时 | 查询时仍在循环累加 | 确认查询代码没有二次遍历矩阵 |
| 结果比预期大 | 容斥公式里加法写多或减法写漏 | 手算小矩阵验证 |
| 结果比预期小 | 漏了左上角 S[x1-1][y1-1] 加回来 | 核对公式四个项是否完整 |
| 越界或访问异常 | 数组没预留 0 行 0 列 | 维度开成 (n+1)*(m+1) |
| 坐标含义反了 | 行列读入顺序理解错误 | 对照题目样例输入输出 |
6.4 版本管理的"模板化"习惯
这个技巧有点特殊，但我觉得值得提一下。很多同学刷题喜欢背模板，但模板一定要背成"自己能改"的版本，而不是死记硬背一串代码。我的做法是维护一个代码模板文件，把预处理和查询公式用注释标清楚：
// 预处理： // s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j] // 查询 (x1,y1) 到 (x2,y2)： // ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]这样在面试或者比赛时，不用现场推导，一眼就能找到对应的代码块。模板写多了以后，你会发现二维前缀和的"可复用性"比想象的高得多，换几个变量名就能适配大部分同类型题。
7. 前缀和思路还能延伸到哪
二维前缀和只是前缀和思想的一个方向，熟练之后还能继续扩展。比如三维前缀和可以处理三维体块的区域和，原理是从二维向前再推一层，容斥项从 4 个变成 8 个，递推公式也会多出几个符号，但思路完全一脉相承。还有差分数组配合前缀和，可以在 O(1) 时间内完成矩形区域的增量更新，适合"多次修改 + 一次查询"的题目类型。
我个人在实际刷题中最大的体会是：前缀和的核心不是那几个公式，而是"预先算好累计信息，用容斥思想快速求局部和"这种思维方式。一旦你习惯带着这种视角去看题目，很多看似无从下手的矩阵题都会突然变得清晰——先预处理，再查表，复杂度肉眼可见地掉下来。
所以如果你正在为子矩阵求和这类题发愁，不用焦虑，拿起纸笔画一张 3×3 的小矩阵，亲手算一次前缀和，再亲手验证一次查询公式，整个过程最多花十分钟，但比背十遍模板都管用。毕竟这个技巧的核心从来不是记忆，而是理解之后可以随时按需重写。等你想明白了这一步，后面的三维版本、差分版本、动态维护版本，其实都是同一棵树上长出来的新枝。
