查询的优化实战)
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]1a[1][2]2a[1][3]3a[2][1]4以此类推。构建前缀和表。先算第一行s[1][1] 0 0 - 0 1 1s[1][2] 1 0 - 0 2 3s[1][3] 3 0 - 0 3 6第二行s[2][1] 0 1 - 0 4 5s[2][2] s[1][2] s[2][1] - s[1][1] 5 3 5 - 1 5 12s[2][3] s[1][3] s[2][2] - s[1][2] 6 6 12 - 3 6 21第三行s[3][1] 0 5 - 0 7 12s[3][2] s[2][2] s[3][1] - s[2][1] 8 12 12 - 5 8 27s[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] 45s[1][3] 6s[3][1] 12s[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 却用了 n1 行 m1 列的下标。前缀和的 0 行 0 列是必须存在的不然递推公式会访问到未定义的值。现场写代码时建议直接把数组维度定义为 N1、M1后面就不用提心吊胆。第二坐标输入顺序搞错。有些题目给的是 (x1, y1, x2, y2)有些给的是 (x1, y1, x2, y2) 但行列顺序反着来。拿到题先看几遍样例确认清楚哪个是行、哪个是列再代入公式。我就见过有人把 x 和 y 反着用样例过了但提交全错后来才发现是读入顺序理解反了。第三数据范围很大时用 int 会爆。一千乘一千的矩阵如果每个元素是 10 的 9 次方级别前缀和早就超过 int 上限了。C 里用 long longPython 虽然随便写但也要注意性能尽量用 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 列维度开成 (n1)*(m1)坐标含义反了行列读入顺序理解错误对照题目样例输入输出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 的小矩阵亲手算一次前缀和再亲手验证一次查询公式整个过程最多花十分钟但比背十遍模板都管用。毕竟这个技巧的核心从来不是记忆而是理解之后可以随时按需重写。等你想明白了这一步后面的三维版本、差分版本、动态维护版本其实都是同一棵树上长出来的新枝。
