ki-pi看到“AcWing 796. 子矩阵的和”这个题，老读者应该瞬间反应过来：这又是二维前缀和的模板题。很多算法入门的朋友第一次卡在前缀和这关，就是被这道题绕晕的——一维前缀和还好说，二维一旦涉及四个格子相加减，脑子里那根弦就绷不住了。这篇就借着这道题，把二维前缀和从公式到代码、从边界到坑，完整拆开揉碎讲清楚。
这题本身是在一个 n 行 m 列的矩阵上做 q 次询问，每次问一个左上角坐标 (x1, y1) 到右下角坐标 (x2, y2) 的这个矩形区域里所有数之和。数据范围是 n、m 最大 1000，q 最大 10 万级别，暴力做的话每次查询要遍历一遍矩形，最坏 O(n*m) 的复杂度，总计算量能到 10 的 11 次方以上，硬跑必超时。所以核心考点只有一个：用二维前缀和，把查询时间压到 O(1)，读完这篇你就能彻底拿下这类矩形求和问题，顺便把一维前缀和的原理也复习得明明白白。适合人群是正在刷算法基础、准备笔试面试、或者想搞懂图像积分图思想的同学。
1. 题目在考什么：子矩阵求和背后那点事
1.1 暴力解法为什么必死
先别急着上公式，我们把没有优化思路时最朴素的做法摆出来，看清楚它到底慢在哪。
假设现在给了一个 3 行 4 列的矩阵，问左上角为 (1, 1)、右下角为 (2, 3) 的矩形和，那就老老实实从第一行第一列扫到第二行第三列，把所有数加起来。单次查询的时间取决于矩形面积，最大就是整个矩阵 n*m。q 次询问，总时间就是 O(q * n * m)。听起来好像也没那么夸张？但当 n、m 取到 1000，q 取到 100000 的时候，q * n * m 是 10 的 11 次方级别的操作。常见的评测机一秒大概跑 10 的 7 到 8 次方次简单运算，这意味着最坏情况下要跑几百上千秒，铁定超时。
有人会想：那多点几次也就多等一会儿，无所谓？不是的，竞赛和算法题考核的核心之一就是复杂度分析，你写了个能算对但算得极慢的程序，本质上就是不合格。所以必须找到一种“预计算”的思路，让每次询问做的计算量跟矩形大小无关，只跟坐标本身有关。
1.2 前缀和的核心思想：提前记账，到时查账
前缀和解决的就是“多次区间求和”这个场景。它做的事情特别像你搞了个记账本：月初你把未来一个月的每一笔开销提前规划好，到了月底问“这个月 5 号到 15 号一共花了多少”，你不需要翻着清单从 5 号加到 15 号，只需要把“到 15 号的累计花费”减去“到 4 号的累计花费”，一减就出来了。
一维前缀和就是这么干的：开一个数组 s，s[i] 表示原数组前 i 个数的和。求 [l, r] 区间和的时候，直接算 s[r] - s[l-1]。这样预处理是 O(n) 的，但每次查询变成了 O(1)，跟区间长度彻底无关。这个思想可以说是整个算法竞赛里性价比最高的一招，学会它，你后面学差分、树状数组时也会轻松很多。
一维里的“区间”是一条线，而二维里的“子矩阵”是一整块面。线段的差分是相减，那面积怎么差？这就引出了二维前缀和的标准做法。
1.3 从一维到二维：面积怎么“减”出来
二维前缀和数组 s[i][j] 的定义是：从矩阵左上角 (1, 1) 到 (i, j) 这个子矩形的所有数之和。
先理解这个定义，再想办法用它来计算任意子矩阵。如果我们要算左上角 (x1, y1) 到右下角 (x2, y2) 的矩阵和，直接用 s[x2][y2] 显然不对，因为它多包含了上面和左边的一大块。但能不能用 s[x2][y2] 减去几块东西得到答案？当然可以，关键是怎么减才不重不漏。
把整个大矩形分成四块区域看：目标区域是中间的深色块，多出来的部分可以看成上方的狭长条、左边的狭长条、以及左上角那个重复减掉的小矩形。所以公式就是：
s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
为什么最后要加 s[x1-1][y1-1]。因为你先减掉了上面那块区域 s[x1-1][y2]，又减掉了左边那块区域 s[x2][y1-1]，左上角那块小矩形在两次减法里都被减掉了，多减了一次，所以要加回来一次。这就是容斥原理，别觉得它玄乎，拿纸笔画一个 5x5 的方格，把每一项覆盖的范围涂掉，一遍就能看明白。
到这里，查询公式有了，但还差最关键的一步：s[i][j] 这个数组本身怎么快速算出来。总不能每个 s[i][j] 都用暴力求和，那预处理就是 O(nmn*m) 了，直接爆炸。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 二维前缀和公式推导与核心细节
2.1 预处理数组怎么构建：四步计算法
s[i][j] 的定义是左上角 (1, 1) 到 (i, j) 的所有数之和。想从已经算好的格子推出当前格子，技巧还是拆面积。
s[i][j] 可以拆成三块已知部分加一个当前元素：
- s[i-1][j]：所有“上面”的格子，也就是从 (1,1) 到 (i-1, j)
- s[i][j-1]：所有“左面”的格子，也就是从 (1,1) 到 (i, j-1)
- a[i][j]：当前格子本身
但注意，s[i-1][j] 和 s[i][j-1] 都包含了左上角那块从 (1,1) 到 (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)，跟查询一个量级。实现时用两层 for 循环：外层从 1 到 n，内层从 1 到 m，逐个计算。
这个公式和查询公式是同构的，都是“两个大矩形减去两个小矩形再加回一个重叠矩形”。你只要能画图理解其中一个，另一个自然就通了。我当年学的时候就是把这个公式背下来，然后做题时在草稿纸上画了一遍推导，从此再没忘过。
2.2 查询公式怎么用：一次询问 O(1) 的关键
预处理完成后，任意一次询问 (x1, y1, x2, y2) 直接套公式：
ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
每次只涉及四次数组访问和三次加减运算，跟 x2-x1 有多大、y2-y1 有多大完全无关，这就是 O(1) 查询。q 次询问的总复杂度就是 O(q)，加上预处理的 O(nm)，整个程序的时间复杂度是 O(nm + q)，稳过 1000*1000 + 10万 的数据。
这里有个关键的边界细节：公式里出现了 x1-1 和 y1-1，当 x1 = 1 或 y1 = 1 的时候，下标会变成 0。这时候 s[0][j]、s[i][0]、s[0][0] 都必须是 0，才不会越界且不影响结果。所以你定义数组的时候要把下标从 1 开始用，然后把第 0 行和第 0 列全部置为 0，这是二维前缀和最典型的边界处理方式。
2.3 边界与下标：为什么老老实实从 1 开始存
很多 C 语言新手习惯于数组下标从 0 开始，写这道题时也默认用 0 到 n-1、0 到 m-1。这也不是不行，但公式会变得非常别扭：你要小心处理 x1-1 变成负数的情况，甚至要特判 x1 是否等于 0。代码可读性会明显下降，而且容易漏判导致越界。
更优雅的做法是输入矩阵时把数据存到 a[i][j]，其中 i 从 1 到 n，j 从 1 到 m，直接把第 0 行第 0 列留着不用，也不去初始化，全局数组默认就是 0。这样查询时 x1-1 最小就是 0，理所当然地落在数组边界内，公式也不需要任何特判。
一个小技巧：读入的时候可以用两层循环 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) 读进 a[i][j]。这也意味着输入文件里的第 1 行第 1 个数，你存的其实不是 a[0][0]，而是 a[1][1]。这是一种“逻辑下标”和“物理下标”偏移一位的存储方式，在算法题中非常常见，只要有区间计算需求，几乎都建议这么干。
有些人在读入时直接构建前缀和，不单独开 a 数组：
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + 当前读入的值
这样也能做，少一个数组的内存，代码也更短。但缺点是很考验你对公式的熟练程度，而且如果题目后面还要用到原矩阵 a 本身的话，就还得另存一份。我建议初学阶段还是老老实实开两个数组：一个存原矩阵，一个存前缀和，等完全熟练了再考虑压缩空间。
3. 完整实现与踩坑实录
3.1 C++ 参考代码（含注释）
直接贴一份我在本地验证过、风格也比较规范的实现。这里用 scanf/printf 而不是 cin/cout，后面会解释为什么。
cpp复制#include <cstdio>
const int N = 1010;
int n, m, q;
int a[N][N];
int s[N][N];
int main() {
scanf("%d%d%d", &n, &m, &q);
// 读入原矩阵，下标从 1 开始
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;
}
把这段代码复制到编译器里，配合随机生成的小矩阵数据和暴力程序对拍，你就知道这个做法到底有多稳。对拍是我非常推荐的一种自查方式：用暴力写法算一个正确答案，再用优化的写法算结果，两者对不上就说明优化代码有 bug。
3.2 Python 参考代码
Python 写这道题也能过，但要注意读入速度和二维数组的初始化方式。最稳妥的写法是用 sys.stdin.read 一次性读入全部数据，然后按索引取用，避免循环里一次次 input 导致 TLE。
python复制import sys
def main():
data = list(map(int, sys.stdin.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):
row_s = s[i]
row_s_prev = s[i - 1]
for j in range(1, m + 1):
row_s[j] = row_s_prev[j] + row_s[j - 1] - row_s_prev[j - 1] + a[i][j]
out_lines = []
for _ in range(q):
x1, y1, x2, y2 = data[idx], data[idx + 1], data[idx + 2], data[idx + 3]
idx += 4
ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]
out_lines.append(str(ans))
sys.stdout.write("\n".join(out_lines))
if __name__ == "__main__":
main()
这里有个小优化：预处理时把 s[i] 和 s[i-1] 取出来放到局部变量里，避免在循环里反复做二维索引查表。Python 在多层循环中的性能差距往往就体现在这种细节上，熟练之后这是很自然的优化手法。
3.3 输入输出的坑：关同步、用 scanf、快读
这道题的数据规模是 n、m 最大 1000，q 最大 10 万。也就是说读入的整数数量在百万级别，输出也在十万级别。用 C++ 的 cin/cout 时，如果没做任何优化，大概率会超时。原因不在于运算本身，而是 C++ 的 iostream 为了兼容 C 风格 stdio，默认做了同步，每次输入输出都有额外开销。解法有两个：
第一，在 main 开头加 std::ios::sync_with_stdio(false); 和 cin.tie(nullptr);，把同步关掉。这样 cin/cout 基本能达到 scanf/printf 的速度。这也是我最推荐的方式，代码写起来比 scanf 舒服。但要注意，关同步之后不能混用 cin 和 scanf、cout 和 printf，否则可能出问题。
第二，干脆像我给出的参考代码一样，直接用 scanf/printf。这个方案不需要关心什么同步问题，是竞赛中最传统也最稳的做法。很多人觉得 scanf 的格式串难写，其实就那么几个固定套路，练一次两次就熟了。
Python 那边也一样，sys.stdin.read 一次读入远比在 for 循环里重复调用 input 快。数据规模大了以后，这些 IO 细节就是决定 AC 还是 TLE 的分水岭。
4. 常见问题与排查技巧实录
4.1 查询结果错乱：多半是边界搞错了
如果你对拍发现结果不对，最大的概率不是公式记错，而是下标边界出了问题。比如你要查 (x1, y1) 到 (x2, y2) 的矩阵，如果 x1 是 2，你应该减掉的是 s[1][y2]，也就是 x1-1 那一行以上的部分，而不是 s[x1][y2]。有些人一紧张就写成 s[x1][y2]，那等于把目标矩阵自己第一行的数据也一起减掉了。
排查方法很简单：拿一个 2x2 或者 3x3 的手算矩阵，把查询下标的每个值代入公式，用纸笔算出期望结果，再和程序输出对比。边界这种错，只要定位了一次，以后同类问题就能形成肌肉记忆。
另外还要注意题目里坐标的含义：这里坐标是从 1 开始计数。有些题的描述可能是 0-based，那就需要先把输入的坐标都加 1 再处理，千万不要生搬公式。
4.2 数组越界或运行崩溃
C++ 里开数组要用 const int N = 1010，然后定义 a[N][N]、s[N][N]，这样下标最多取到 1000，而 n 和 m 最大也是 1000，刚刚够用。但如果你想省事，把 N 开成 1005 甚至 1010 以上都是安全的，稍微富余一点可以防止写错时越界访问。
还有一类越界是访问 a[0][...] 或 s[0][...] 时，本意可能是想访问第 1 行，但因为下标没加偏移导致访问到了第 0 行。第 0 行在全局变量里是 0，逻辑上好像没错，但如果你用局部变量或者动态分配，这块内存可能是未初始化的垃圾值，结果就会飘。所以再次强调：所有数组要么全局变量，要么初始化成全 0。
Python 里不会越界崩溃，但是会报 IndexError，本质原因和 C++ 一样：下标习惯性偏移一位处理错了。判断方法：看报错的行是访问 a[x1-1][...] 还是 s[...][y1-1]，在那个位置打印出对应下标值，一眼就能发现问题。
4.3 有人问：能不能不额外开前缀和数组
理论上是能的。你可以在原矩阵 a 的基础上原地修改，让 a[i][j] 变成前缀和 s[i][j]。做法还是用同样的递推公式，只不过直接把结果写回原位置：
cpp复制for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
}
这样省了 s 数组的空间，从 2 * 1001 * 1001 个 int 变成 1 个 1001 * 1001 的 int，内存几乎减半。对于这道题来说，省不省其实无所谓，但如果你在做一个超大矩阵、内存紧张，原地转换就派上用场了。不过前提是原矩阵后面不再使用，否则原数据会被覆盖掉。
这种“原地前缀和”的技巧本质上就是空间换时间的不同取舍，不影响复杂度分析。我一般建议新手先写分离版本，确保思路清晰，然后再尝试原地版本，体会一下两种写法的区别。
5. 同类题扩展与思维迁移
5.1 不只是矩阵求和：积分图与图像处理
二维前缀和这个思想在真实工业界有个很有名的名字，叫积分图（Integral Image），是图像处理里非常重要的工具。比如要实现一个“模糊滤镜”，需要对图像任意矩形区域做像素值求和，如果每次实时计算，代价是不可接受的。用积分图预计算一遍，之后不管滤波器窗口多大，每次求和都是 O(1)，整体性能就能从 O(窗口大小) 降到 O(1)。
你甚至可以把一张灰度图想象成一个矩阵，每个像素点就是矩阵元素，然后对它做二维前缀和。后面做窗口滑动、区域亮度统计、人脸检测里的 Haar-like 特征计算，都会用到同一套思想。所以别觉得这题只是考试用，它背后的原理是能迁移到真实场景中的。
做题的人常常忽略这个联系，觉得“积分图”是个很高端的东西。其实它就是二维前缀和换了个名字，原理一模一样。你在 AcWing 上 AC 了这道题，相当于已经把图像处理里一个基础而重要的工具学明白了。
5.2 一维差分和二维差分的预告
前缀和有一个对应的逆操作，叫差分。如果说前缀和是“预处理后快速求区间和”，那差分就是“先记录区间增量、最后一次性还原每个点的值”。很多题看起来是区间整体加一个数，比如“给 (x1, y1) 到 (x2, y2) 矩形内所有元素加 c”，如果暴力更新每个元素，复杂度就是矩形面积；但用二维差分数组，只更新四个角，最后做一次前缀和还原，就能把复杂度降到 O(1) 更新、O(n*m) 还原。
差分和前缀和是成对出现的。理解了二维前缀和，二维差分的四个更新点几乎就是“查询公式的镜像操作”。所以这个题并不是孤立的模板题，它同时为你打开了差分的大门。学算法的时候这种前后钩连很重要，不要为了 AC 而 AC，要把公式和思想建立成网络。
5.3 动态维护的历史总量问题
现实生活中还有一类场景：你记录了某产品每天的销量，老板随时会问“某段时间到某段时间的总销量是多少”。直接用前缀和就能回答。如果把日期扩展成两个维度，比如“不同地区”和“不同时间”，那本质上就是一个二维矩阵，每个格子是某一地区某一天的销量，问“某地区某时间段的总量”就是子矩阵求和。
我见过不少做数据报表的同学，用 SQL 或者 Excel 硬算这类问题，数据量小的时候无所谓，一旦数据量涨起来，每次都全表扫描就非常吃力。理解了二维前缀和的思路后，你会下意识地想：能不能提前建一张“累计汇总表”，让查询变成 O(1)？这种思维方式的迁移，比多会一个模板题重要得多。
6. 从这道题延伸出去的几个实用技巧
6.1 用一个小数据带跑通全流程
学任何模板题，我强烈建议你用最笨的方法先跑一遍。拿一个 3x3 的手写矩阵，比如：
code复制1 2 3
4 5 6
7 8 9
先手工算出 s 数组：
s[1][1] = 1
s[1][2] = 3
s[1][3] = 6
s[2][1] = 5
s[2][2] = 12
s[2][3] = 21
s[3][1] = 12
s[3][2] = 27
s[3][3] = 45
再随便查一个子矩阵，比如 (2, 2) 到 (3, 3)，期望答案是 5 + 6 + 8 + 9 = 28。用公式算 s[3][3] - s[1][3] - s[3][1] + s[1][1] = 45 - 6 - 12 + 1 = 28，完全正确。这种手算过程能帮你把抽象公式具象化，比记任何口诀都管用。
6.2 一个很隐蔽的重复计算问题
有人会在预处理之后，嵌套三层循环来算答案：比如 for (i = x1; i <= x2; i++) for (j = y1; j <= y2; j++) ans += a[i][j]，然后发现每层循环里又调用前缀和数组——这种混用等于没有优化，该超时还是超时。正确做法是查询时彻底放弃循环遍历，只套公式，一次解决。
尤其是当 q 很大、矩形很小时，有些同学会觉得“反正矩形小，暴力也没事”。千万不能这么想，因为最坏情况不是你能控制的，评测数据里一定有让你超时的极限用例。算法的本质是保证最坏情况下依然高效，而不是赌数据善良。
6.3 坐标公式记忆法
有一句很朴实的话你可以记一下：查询子矩阵，先用大矩阵，剪掉上方和左方，补回左上角。预处理当前格子，等于上边加左边，减去左上角，最后加当前值。这两句话是同一个逻辑背了两遍，永远不要分开记，不然做着做着就串了。
我觉得最有用的方法其实是自己动手画。每学一种算法题，找一张草稿纸，把矩阵格子画出来，把公式里每个项对应的区域涂上不同颜色。这个过程最多耗时五分钟，但对公式的理解深度远超读十篇题解。
7. 这题还能怎么变着考
7.1 子矩阵最大和问题
如果你已经熟练掌握了子矩阵的和，可以接着挑战“最大子矩阵和”问题：找矩阵中的一个子矩阵，使得它的元素和最大。这个问题的经典做法就是枚举矩阵的上下边界，将列方向压缩成一维数组，然后跑一遍一维最大子段和。核心依然离不开前缀和，你要快速计算任意子矩阵的和，才能把每一对上下边界之间的压缩数组快速求出来。
这个变形在不少大厂的笔试中都能见到身影，解法本质上就是“二维枚举 + 一维动态规划”。如果做这道题只是为了背公式，是很难迁移过去的；但如果你理解了子矩阵求和能快速算出任意矩形区域的和，那么最大子矩阵和题就会变得顺理成章。
7.2 带修改的矩阵求和
如果题目不仅询问子矩阵和，还会随时更新矩阵中某个元素的值，最简单的前缀和就没法直接用了。这时候要引入二维树状数组或二维线段树。它们的使用场景不同，但基础定位仍然是“区域聚合查询”。
这种题的难点跨了一个台阶，但理解二维前缀和仍然是必要的前置。因为二维树状数组维护的照样是某种前缀关系，只是它支持了单点更新。如果你在做题时有计划地进阶，这个梯度是很清晰的：先暴力 → 再前缀和 → 再树状数组 → 再线段树。
7.3 不规则区域求和
有时候题目要算的不是矩形，而是三角形、圆形、或者任意多边形内部的元素和。这类题在竞赛里也有套路，但底层思想依然和二维前缀和有关。一个常用手段是把多边形切成若干梯形或者矩形，再利用前缀和快速求得每一块的面积和，最后合并。
虽然听起来很数学，但本质还是“区域快速求和”，只是把区域切割成若干个可用公式计算的子区域。能把这个想明白的人，对二维前缀和的理解就已经超出模板层面了。
8. 实操总结与个人体会
这道 AcWing 796 的二维前缀和题，做完了之后我最大的体会是：很多算法说穿了就是一层窗户纸，难点不在于“理解”，而在于“熟”。我第一次接触这个公式的时候也很懵，为什么预处理还要加回来一个 s[i-1][j-1]？为什么查询也要加回来一个 s[x1-1][y1-1]？后来手画了几遍图，才真正建立起空间直觉。
另一个体会是，这种模板题的代码一定要固定下来，形成自己的肌肉记忆。不是要你死记硬背，而是要把“从 1 开始存、预处理四步、查询四步、用 scanf 或关同步”这些关键决策固化成默认选项。等你在赛场上或面试手写算法时，这能省下大量思考时间，把它们留给真正有挑战性的部分。
最后再分享一个小技巧：做题时如果时间允许，写完优化解法之后，顺手写一个暴力解法做对拍。用 Python 的随机数据生成器，跑个几十组小规模数据，一次就能验证解法的正确性。很多人认为自己公式记熟了就不会错，但边界问题、下标偏移问题，往往是在对拍中暴露出来的。这个习惯一旦养成，刷题出错率能明显降下来。