刷题刷到子矩阵的和的时候我一开始真没当回事不就是一个矩阵里反复求和嘛for循环一套不就完事了直到数据范围拉满、评测超时的那一秒我才意识到二维前缀和这套模板必须从头啃透。后来我把这道经典题——通常就是OJ题库里的796题——研究明白后才发现它不仅是二维前缀和的入门模板更是很多矩形区域查询类问题的基本功底。这篇文章我会从暴力为什么超时讲起把二维前缀和的预处理公式、查询公式、模板代码、以及各种易错点全部放开讲一遍。适合刚学完一维前缀和、正处于二维怎么搞阶段的读者也适合想彻底背下这套模板、以后不再丢分的竞赛刷题党。1. 一维前缀和到二维的跨越暴力TLE之后我悟了1.1 暴力代码为什么必挂复杂度那笔账先看最直观的写法给定一个 n×m 的整数矩阵和 q 次询问每次给出左上角坐标 (x1,y1) 与右下角坐标 (x2,y2)求这个子矩阵内所有元素的和。新手的自然反应是四层循环int sum 0; for (int i x1; i x2; i) for (int j y1; j y2; j) sum a[i][j];这段代码逻辑完全正确真挑不出毛病。问题全在效率单次询问的最坏情况是整个矩阵那么大也就是说要做 O(n*m) 次加法。假如矩阵是 1000×1000查询次数是 100000那总运算量就是 1000×1000×100000 10^11 次。评测机一秒钟通常能扛住 10^8 到 10^9 次简单运算10^11 是什么概念哪怕时间限制给 2 秒暴力写法连边都摸不到。所以问题的关键不是能不能算对而是如何把单次查询从 O(nm) 降到 O(1)。但天下没有免费的午餐想让查询变快就得在读入数据之后先花 O(nm) 的时间做预处理。这就是前缀和思想的核心把反复用到的重复计算一次性铺垫好。1.2 一维前缀和是二维的钥匙一维前缀和是所有人都绕不过去的入门内容。给定数组 a[1..n]求区间 a[l..r] 的和。先预处理 S[i]S[i-1]a[i]然后查询时直接输出 S[r]-S[l-1]。为什么这个减法成立因为 S[i] 存的是从第 1 个数到第 i 个数的累计和。求 [l,r] 的和本质就是拿前 r 个数的总和减去前 l-1 个数的总和中间那段自然就剩下来了。二维前缀和就是同一思想的升维一维用一次减法换一段区间和二维用一次加加减减的组合换一块矩形区域和。我强烈建议先在心里把一维的代码默写一遍因为二维预处理公式里的 S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]本质上就是累加、合并、去重三个动作的组合。一维那个减一次没搞明白二维这个减两次加一次就更容易晕。拿表格对比一下维度预处理复杂度单次查询复杂度空间复杂度一维前缀和O(n)O(1)O(n)二维前缀和O(n*m)O(1)O(n*m)一维到二维空间和时间都多了一个维度但查询 O(1)这个核心优势保留了下来。1.3 为什么不能只按行做前缀和有的读者可能会问我每一行单独做一维前缀和然后查询时把 x1 到 x2 的每一行区间和加起来行不行当然行但那样单次查询的复杂度是 O(x2-x11)也就是 O(n)。如果查询次数多、矩阵行数大这仍然不够快。二维前缀和的精髓在于把行方向也通过容斥处理成 O(1)所以它才是这类题的标准解法。理解了这个差别就明白为什么二维前缀和被单独作为一个模板题了——它是一个从一维思维升级到二维容斥思维的分水岭。2. 二维前缀和的预处理公式容斥原理的正确打开方式2.1 S[i][j] 到底存的是什么先做个重要约定数组下标从 1 开始。设 a[i][j] 是原矩阵第 i 行第 j 列的值定义 S[i][j] 表示以 (1,1) 为左上角、(i,j) 为右下角这个子矩阵内所有元素的和。注意S[i][j] 是一个前缀矩形的总和不是某个点上的值。举个小例子假设矩阵是1 2 3 4 5 6 7 8 9那么 S[2][2] 1245 12也就是左上角那个 2×2 小方块里的数字全加起来。按定义直接算的话每个 S[i][j] 都要加 O(ij) 个数整体预处理会变成 O(n²m²)跟暴力没有本质区别。所以必须找到相邻格子之间的递推关系用已算好的值去推出新的值。2.2 递推公式的推导用画图代替死记看 S[i][j] 和 S[i-1][j]、S[i][j-1] 的关系。S[i-1][j] 是包含前 i-1 行、前 j 列那个矩形的和S[i][j-1] 是包含前 i 行、前 j-1 列那个矩形的和。如果直接把这两个加起来会发现左上角那个前 i-1 行、前 j-1 列的矩形区域被加了两次而右下角 a[i][j] 这个点还一次都没加。于是需要做两件事减去重复加了一次的区域补上还没加进来的当前格S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]这就是容斥原理最朴素的一种形态——求两个有重叠区域的面积之和时先相加再扣掉重叠部分。S[i-1][j-1]就是那个重叠部分。我用上面的 3×3 矩阵验证一下S[2][2] S[1][2] S[2][1] - S[1][1] a[2][2] (12) (14) - 1 5 12完全吻合。2.3 查询公式把目标子矩阵从大矩形里切出来预处理完成后S 数组里存的全是从左上角出发的矩形和。现在要查询 (x1,y1) 到 (x2,y2) 的这一块怎么从这些大矩形里拼出来思路同样是容斥先用 S[x2][y2] 表示整个左上角到 (x2,y2) 的大矩形然后去掉坐标 x1 上面的部分再去掉坐标 y1 左边的部分。但这两刀切完后左上角那块既在上方又被切掉的小矩形被减了两次所以要再加回来一次。于是得到查询公式ans S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] S[x1-1][y1-1]继续用上面的矩阵验证查询 (2,2) 到 (3,3)期望值 5689 28代入公式ans S[3][3] - S[1][3] - S[3][1] S[1][1] 45 - 6 - 12 1 28结果正确。整个过程就是大矩形减上边减左边再把左上角加回来一共三次加减O(1) 完成。3. 模板代码拆解下标从1开始才是灵魂3.1 一套可以直接默写的 C 模板这是我在 OJ 上反复提交过的模板稳定 AC结构如下#include cstdio const int N 1010; int a[N][N], s[N][N]; int main() { int n, m, q; scanf(%d%d%d, n, m, q); for (int i 1; i n; i) for (int j 1; j m; j) scanf(%d, 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]; while (q--) { int x1, y1, x2, y2; scanf(%d%d%d%d, x1, y1, x2, y2); printf(%d\n, s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] s[x1 - 1][y1 - 1]); } return 0; }核心代码就两段一个预处理二重循环一条查询输出语句。读入的部分只是把数据装进去。这个结构的固定程度非常高背下来之后基本就是默写变来变去也只需要改 N 的大小、换一下输入函数。如果你习惯用 cin/cout记得在 main 开头加上这两行ios::sync_with_stdio(false); cin.tie(nullptr);不然 n、m 到 1000、q 到 10 万级别时输入输出开销可能会卡掉一两个测试点。这不是玄学是 C 的 cin 默认要和 C 标准 IO 做同步带来的额外成本关掉之后就快很多。3.2 为什么下标从 1 开始而不是从 0 开始很多从 Python 或 JavaScript 转过来的读者不习惯下标从 1 开始总觉得别扭。但我强烈建议在矩阵前缀和类题目里一律从 1 开始开数组。原因在查询公式里已经埋下了伏笔里面出现了 x1-1 和 y1-1。如果下标从 0 开始查询第 0 行或者第 0 列时就会出现 -1直接数组越界。虽然可以特判 if (x1 0) 之类的但每个查询都得判断代码啰嗦还容易写错。从 1 开始的话S[0][] 和 S[][0] 天然就是 0公式直接生效一行特判都不需要。这就是典型的用空间换代码简洁。数组多开一圈边界条件全部消失。我见过太多从 0 开始的硬核选手不是忘了特判就是特判写错半天调不出来。3.3 一个隐藏技巧预处理时直接覆盖原数组严格来说不需要把 a 和 s 两个数组都开出来。读入时直接让 s[i][j] 存原始值再做预处理也是可以的for (int i 1; i n; i) for (int j 1; j m; j) scanf(%d, s[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];这里有个关键点第二个循环里右边用到的 s[i-1][j]、s[i][j-1]、s[i-1][j-1]在当前格被更新之前其存储位置已经在行或列上靠前它们已经被更新为前缀和了所以 的顺序不会出错。这种写法的意义在于数组数量减半、内存占用更小。n、m 到 1000 时无所谓但矩阵大到 3000×3000 时内存吃紧就能派上用场。不过对新手我建议先老老实实用两个数组逻辑更清晰等理解透了再合并也不迟。4. 796题完整解题从读题建模到AC代码4.1 题面说人话OJ题库里的 796 题题面大致如下给定一个 n 行 m 列的整数矩阵再给 q 次询问每次询问给四个整数 x1、y1、x2、y2分别表示左上角和右下角的坐标要求输出这个子矩阵内部所有数的和。数据范围一般是 n,m ≤ 1000q ≤ 100000。翻译成人话给你一个二维数组反复让你取某个矩形区域的和一次都不能算错时间还得够快。这道题是纯模板题只要二维前缀和写熟了一次过的概率极高。它能成为模板题正是因为把所有必须理解的点都浓缩在一个场景里预处理要算哪些矩形、查询怎么把目标区域切出来、边界要不要特判。这些在上面几节里已经全部覆盖到了。4.2 完整 AC 代码标准的 C 提交版#include cstdio const int N 1010; int a[N][N], s[N][N]; int main() { int n, m, q; scanf(%d%d%d, n, m, q); for (int i 1; i n; i) { for (int j 1; j m; j) { scanf(%d, 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]; } } while (q--) { int x1, y1, x2, y2; scanf(%d%d%d%d, x1, y1, x2, y2); int ans s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] s[x1 - 1][y1 - 1]; printf(%d\n, ans); } return 0; }这段代码在 n、m 上限 1000、q 上限 100000 的范围内实测运行时间一般只有几百毫秒距离时间限制有充足余量。这里要单独说一个容易翻车的点类型选择。如果矩阵元素绝对值不超过 1000矩阵大小是 1000×1000那 s 数组里最大的前缀和是 10^9 级别int 能装下。但如果题目说明每个元素可能到 10^9那么前缀和最大就能到 10^15 级别必须用 long long不然会 WA 到怀疑人生。判断标准很简单最坏情况下所有元素之和会不会超过 int 范围会就换 long long。4.3 复杂度验证预处理阶段两个嵌套循环每个位置做常数次运算总计 O(nm)。查询阶段 q 次询问每次 O(1)。整体复杂度 O(nm q)。对比暴力方案 O(qnm)这是数量级上的差异。我常打一个比方如果矩阵是 1000×1000暴力做一次最坏查询要扫 100 万个位置而前缀和方案只需要从 s 数组里取 4 个数做 3 次减法、1 次加法。一个是百万量级的工作量一个是四个数的计算量这就是前缀和的核心价值。5. 模板的延伸用法二维差分与多语言实现要点5.1 二维差分前缀和的逆运算二维前缀和解决的是静态矩阵反复查询子矩阵和的问题。如果把问题反过来——初始矩阵全 0要执行很多次把某个子矩阵内所有数加上 c的操作最后求最终矩阵——这就是二维差分的场景。差分数组 d 的定义是对 d 做二维前缀和之后能得到原矩阵 a。也就是说 d 是 a 的前缀和源头。如果只在 d[x1][y1] 处加 c那么做前缀和后从 (x1,y1) 到右下角的整个矩形都会增加 c。要让增加量精确落在 (x1,y1) 到 (x2,y2) 这个子矩阵内需要在四个位置打标记d[x1][y1] c; d[x2 1][y1] - c; d[x1][y2 1] - c; d[x2 1][y2 1] c;然后再对 d 做一次二维前缀和得到的就是所有修改叠加后的最终矩阵。四角标记和查询公式里的减减加加来自同一个容斥原理只是方向相反。很多矩形区域加值、最后问每个点最终值的题目本质就是二维差分 二维前缀和的组合题。5.2 Python 实现注意点Python 写同样的模板有几个坑要避开。第一二维数组初始化不能用[[0] * (m 1)] * (n 1)这样每一行都是同一个列表对象的引用改一行会传染到所有行。正确写法是[[0] * (m 1) for _ in range(n 1)]。第二读入要用sys.stdin.buffer.read().split()一次性读入并转成 int不要逐行 input()。q 到 10 万时逐行读的 IO 开销可能直接让 Python 版被卡掉一半时间。第三Python 的 int 没有溢出风险省心但整体速度偏慢矩阵特别大时慎用。给一个简洁的 Python 模板import sys data list(map(int, sys.stdin.buffer.read().split())) idx 0 n, m, q data[idx], data[idx 1], data[idx 2] idx 3 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): for j in range(1, m 1): a[i][j] data[idx] idx 1 for i in range(1, n 1): for j in range(1, m 1): s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1] a[i][j] out [] for _ in range(q): x1, y1, x2, y2 data[idx], data[idx 1], data[idx 2], data[idx 3] idx 4 res s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] s[x1 - 1][y1 - 1] out.append(str(res)) sys.stdout.write(\n.join(out))sys.stdin.buffer.read().split()一次性把数字全部读进来配合list(map(int, ...))比逐行读快一个量级实战中非常管用。输出的部分也是一样先拼到一个列表里最后一次性 join比循环里每次 print 快很多。5.3 边界情况的处理二维前缀和模板里最容易被忽略的就是边界。好在从 1 开始的下标设计已经自动处理掉了一部分当 x11 时x1-10S[0][y2] 为 0公式照样成立。整行或整列的子矩阵也同理。但数组大小必须注意如果开的是int s[1005][1005]而 n、m 上限是 1000那访问 s[1000][1000] 是安全的但如果题目上限是 1000 而你开了int s[1000][1000]访问 s[1000][1000] 就会越界。我的习惯是常量统一大一级比如上限 1000 就开 1010上限 10000 就开 10010多开一点不心疼。还有一个经常出现在翻译题目环节的问题有些题目的坐标是 0-based也就是从 0 到 n-1。这种时候读入坐标后要手动加 1转成模板里的 1-based 坐标否则公式里的 x1-1 在 x10 时又会越界。6. 我走过的弯路越界、公式记混与类型溢出6.1 我踩过的坑排行先说结论按出现频率从高到低排第一预处理循环写反或漏层。这种现象一旦出现s 数组里全错但程序不报错排错时特别难受。我的习惯是写完先用一个小矩阵手算两个 S 值比如 S[2][2]跟纸上算的对一下匹配再提交。第二查询公式加减位置记混。减号一多就容易晕比如把公式写成 S[x2][y2] - S[x1-1][y1-1] - S[x1-1][y2] S[x1-1][y1-1] 这种漏掉一个、重复一个的组合。我的记忆方式是六个字大减上减左加回左上角。每次写完心里默念一遍。第三数组开小了。上节提到过n、m 最大值是多少数组就至少要在最大值基础上加 1。多开 10 个 int 几乎不占内存但能省下一堆越界问题。第四int 溢出。矩阵元素大时用 long long这个坑在前面的 4.2 里已经详细说过了最坏情况算一遍 sum 就知道答案会不会爆 int。6.2 快速验证模板对不对的方法提交之前本地跑一个小样例是最稳的。我常用的方法是用题目自带的样例数据在代码里硬编码跑一遍并且临时打印出 S 矩阵的前几行前几列人肉对照验证。调试打印代码长这样// 调试专用提交前记得注释掉 for (int i 0; i n; i) { for (int j 0; j m; j) { printf(%d , s[i][j]); } puts(); }把 s 矩阵打印出来用肉眼对照手算的结果基本能定位所有预处理错误。还有一个经验如果样例 1 对了样例 2、3 错了那多半是某个角落的边界问题比如坐标没做 0-based 到 1-based 的转换或者数组开小了导致内存越界但没崩。6.3 记忆口诀与后续进阶方向最后分享一套我帮很多人整理过的记忆口诀预处理上加左减左上再加自己。查询大矩形减上方减左方加回左上。这两句话也适用于二维差分加 c 位置四处改右下界外各减一。等这四句话能直接脱口而出这套模板就算真正长在手上了。接下来可以练习的方向包括求最大子矩阵和用列压缩配合一维前缀和或动态规划思路矩形区域内不同元素种类计数配合状态压缩或哈希再进阶就是把二维前缀和扩展到三维三维容斥的公式更复杂些但核心思想是一模一样的。我在刚学这道模板题时也是背了又忘、忘了又背。真正让我彻底记住的办法很简单自己把 3×3 的矩阵画了不下十遍再把模板默写了不下二十遍。现在遇到任何二维区间查询的题目第一反应就是这套模板连调试时间都省了。建议你也给自己定个小目标——不看任何参考在白纸上把预处理公式和查询公式各推一遍再把代码默写一遍。这两件事做完二维前缀和就再也不会从你脑子里跑掉了。