二维前缀和详解：子矩阵的和如何从暴力到O(1)查询

如果你在算法练习平台上刷到编号 796 这道《子矩阵的和》，大概率已经被“给一个矩阵、几千次询问”的暴力解法折磨过一轮了。这题真正的考点只有一个：二维前缀和。它不考什么高深数据结构，也不需要你背复杂的模板，但能不能把两条核心公式彻底理解透、把边界情况一次写对，往往决定了你是五分钟轻松 AC，还是反复提交超时、越界、答案错乱。

这篇文章我不重复贴题面，而是把整个思考链路拉出来讲一遍：题目想让我们干什么、暴力为什么不行、二维前缀和的两条公式到底怎么来的、代码怎么写最稳、实际提交时最容易踩哪些坑，以及做完这道题之后还能顺带掌握哪些进阶内容。无论你是刚学前缀和的新手，还是准备面试、竞赛想快速复习，这篇都值得看完。

1. 拆开题目：它到底考的是哪种预处理

1.1 题面拆解与输入输出示例

先看一眼题目的核心结构。输入会先给你三个数 n、m、q，表示一个 n 行 m 列的矩阵，以及 q 次询问。接下来是一个 n 行 m 列的整数矩阵。再接下来有 q 行，每行四个整数 x1、y1、x2、y2，表示查询左上角 (x1, y1) 到右下角 (x2, y2) 这个矩形区域的所有数字之和。

比如下面这组数据：

text复制3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

第一行表示矩阵是 3 行 4 列，有 3 次询问。矩阵内容如下：

• 第 1 行：1 7 2 4
• 第 2 行：3 6 2 8
• 第 3 行：2 1 2 3

三次询问分别输出：

text复制17
27
21

这里我手动验证一下第二个询问：左上角 (2,1)、右下角 (3,4)，覆盖的是第 2 行和第 3 行的全部 4 列。第 2 行是 3+6+2+8=19，第 3 行是 2+1+2+3=8，加起来总共 27，正好和输出对得上。这种小样例我建议你在看完这篇文章后自己手算一遍，对理解公式非常有帮助。

1.2 暴力做法为什么不可行

最直觉的写法是每次询问都从 (x1, y1) 双层循环累加到 (x2, y2)。代码确实简单，但复杂度完全扛不住。

假设 n、m 都是 1000，那么整个矩阵就有 100 万个元素。一次询问如果问的是整个矩阵，就需要做约 100 万次加法。如果 q 是 1000 次，那就是 10 亿次操作。这个量级在 C++ 里可能勉强压线，但换成 Python 基本可以直接宣告超时。如果 q 是 10^5，哪怕每次只查一个很小的区域，因为数据范围的不确定性，最坏情况下依然会慢得离谱。

暴力慢在哪？慢在每次查询都把大量数字重新加了一遍。如果我们能提前把“所有可能用到的累加结果”都算好存在一个表里，查询时只做几次加减法，那就能把复杂度从“每次询问 O(n*m)”降到“每次询问 O(1)”。这张表就是二维前缀和数组。

2. 二维前缀和的两条核心公式是怎么推出来的

2.1 从一维前缀和到二维的迁移

一维前缀和大家都熟：有一个数组 a，定义 s[i] = a[1] + a[2] + ... + a[i]。构建时用 s[i] = s[i-1] + a[i]，查询区间 [l, r] 的和时用 s[r] - s[l-1]。这里的核心思想是“先求从头到某个位置的累计值，再做差得到局部区间”。

二维前缀和就是把这套思想从一条线扩展成一个面。我们定义 s[i][j] 表示原矩阵中从左上角 (1,1) 到右下角 (i,j) 整个矩形区域的所有元素之和。只要这个 s 算好了，任意一个 (x1,y1) 到 (x2,y2) 的矩形和，理论上就可以由几个 s 的值组合出来。

所以整个问题被拆成了两半：怎么构建 s，以及怎么用 s 查询任意子矩阵。

2.2 预处理公式的容斥推导

构建 s[i][j] 时，我们不能每次重新累加一个矩形，那样复杂度又回去了。要用递推。

s[i][j] 表示从 (1,1) 到 (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-1]。如果不把重叠部分去掉，它就被加了两次。所以递推公式是：

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

这个 - s[i-1][j-1] 就是整个公式唯一看起来“多余”却又绝对不能少的一项。它的本质是容斥原理：两个区域相加，扣掉多算的重叠区，再补上当前点。

拿二维数组来验证。假设置 a 数组如下：

按公式递推：

• s[1][1] = 0 + 0 - 0 + 1 = 1
• s[1][2] = s[0][2] + s[1][1] - s[0][1] + 2 = 0 + 1 - 0 + 2 = 3
• s[2][2] = s[1][2] + s[2][1] - s[1][1] + 5 = 3 + 5 - 1 + 5 = 12

而手工加一下 1+2+4+5 也正好是 12。到这里你其实已经把最难的部分消化掉了。

2.3 查询公式的容斥推导

s 构建好之后，任意查询都不需要再去扫描原矩阵了。查询 (x1,y1) 到 (x2,y2) 的和时，先把 s[x2][y2] 拿出来，这是从 (1,1) 到 (x2,y2) 的大矩形。

这个大矩形比我们想要的多了两块：

• 上面多出了从 (1,1) 到 (x1-1, y2) 的矩形，也就是 s[x1-1][y2]。
• 左边多出了从 (1,1) 到 (x2, y1-1) 的矩形，也就是 s[x2][y1-1]。

但这两块多出来的区域之间也有重叠，重叠部分是从 (1,1) 到 (x1-1, y1-1) 的矩形，也就是 s[x1-1][y1-1]。因为它在刚才两次减法中被扣了两次，所以要加回来一次。

最终查询公式：

sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

我当初学的时候很容易把加减号背混。后来我养成了一个习惯：不背公式，而是画图。每一次都把“减去上边、减去左边、加回左上角重叠区”这个动作在纸上画一遍，画两三次之后符号就再也错不了。

还是用刚才的 3x3 矩阵，查 (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，完全一致。

3. 代码落地：从输入到输出一次写对

3.1 用 1-based 下标，省掉所有边界特判

写这题，我强烈建议把数组下标从 1 开始，而不是 C 语言原生的 0。原因很简单：题目给出的坐标就是从 1 开始的。如果你用 0-based，那么查询公式里的 x1-1 可能会变成 -1，每次都要做偏移判断，代码丑不说，还特别容易出 bug。

用 1-based 之后，s[0][j] 和 s[i][0] 自然全是 0。递推和查询都不需要特判“第一行”“第一列”的情况。这也是竞赛圈处理二维前缀和的通用习惯：数组开成 (n+1) 行 (m+1) 列，多出来的一圈 0 专门用来兜底。

3.2 C++ 参考实现与注释

下面这份代码是逻辑最清晰的版本，适合新手照着敲。我把原数组和前缀和数组分开，方便对比理解。

cpp复制#include <cstdio>

const int N = 1010;
int a[N][N];
long long 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("%lld\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }

    return 0;
}

这里我特意把 s 声明成 long long。你可能会觉得矩阵里数字看起来不大，但别拿自己的提交去赌数据范围。如果矩阵每个元素是 10^9，一个 1000x1000 的子矩阵总和就能到 10^15，int 完全装不下。用 long long 是最稳妥的。

如果你想更省内存，可以不保留 a 数组。读入第 i 行第 j 列的值 val 时，直接执行：

cpp复制s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + val;

前提是遍历顺序必须是从左到右、从上到下。因为 s[i][j] 依赖的 s[i-1][j] 和 s[i][j-1] 都必须在它之前算完。这种做法我后来越用越多，省一个二维数组，代码也更紧凑。但如果你是第一次写，我还是建议先开两个数组，把原矩阵和前缀和矩阵分开，出了 bug 也好对照排查。

3.3 Python / Java 写法要注意什么

Python 版本核心思路一样，但性能问题必须重视。n 和 m 最大到 1000，矩阵已经有 100 万个元素，q 又可能很大，纯 Python 裸跑很容易超时。我的建议是至少用 sys.stdin.readline 按行读，输出也别一条条 print，而是先存到一个列表，最后用 '\n'.join 一次性输出。

python复制import sys

input = sys.stdin.readline
n, m, q = map(int, input().split())

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):
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + row[j - 1]

out = []
for _ in range(q):
    x1, y1, x2, y2 = map(int, input().split())
    ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]
    out.append(str(ans))

sys.stdout.write("\n".join(out))

这段代码我在 n=m=1000、q=10^5 的规模下实测过，PyPy 能稳定通过，瓶颈基本只在 I/O。Java 版核心循环一样，用 BufferedReader 加 StringTokenizer 读入，别在查询循环里反复做字符串拼接。需要注意的仍然是 long 而不是 int 存前缀和。

4. 现场排查：我见过的翻车点合集

4.1 数组开小与循环边界错误

除了题目本身，这是最常见的错误。很多人想着矩阵是 n 行 m 列，就开一个 s[n][m]，结果递推式里访问 s[i-1][j] 时，i=1 会访问到 s[0][j]，如果数组下标从 0 到 n-1，这个访问直接越界。正确做法是开 s[n+1][m+1]。

循环边界也值得多说一句。既然下标从 1 开始，外层循环条件就是 i <= n，不是 i < n。我见过有人写着写着又切回 0-based 的习惯，结果最后一行永远没有进入前缀和计算，所有查询结果都少了一部分数据。最笨也最有效的排查方法是拿 n=1 的极端数据去试：n=1 时循环必须从 1 跑到 1，所以条件必须是 i <= n。

4.2 int 溢出与数据范围

前缀和数组存的是“从左上角到某个位置”的累计结果，矩阵越大，累加值越大。如果原矩阵元素范围比较极端，int 溢出就是定时炸弹。而且这种溢出非常隐蔽，因为小数据测试时可能完全正常，只有在最大数据量下才爆炸。

我的原则很简单：所有涉及二维前缀和的题，一律用 long long。现代评测机处理 64 位整数并不比 32 位慢多少，换来的却是数据范围层面的绝对安心。别为了省那一点内存去赌数据温和，哪怕真的超内存风险，也不是在这个基础模板上考虑的事。

4.3 输入输出的性能陷阱

数据量大的时候，cin/cout 的默认同步模式会慢到让你怀疑人生。如果你用 C++ 的 iostream，记得在 main 开头加：

cpp复制ios::sync_with_stdio(false);
cin.tie(nullptr);

或者干脆用 scanf/printf，省心又稳定。Python 的 print 同理，能少调用就少调用，一次性拼接输出往往比循环里 print 快一个量级。

还有一个容易被忽略的点：如果你用 scanf 读一个 1000x1000 的矩阵，单次调用 100 万次 scanf 的解析开销其实不小。更极限的优化是把整行读成字符串再解析，但一般比赛里用不到。知道这件事的存在就够了，真正卡 IO 极限的题目会用更激进的输入手段。

4.4 一个小型调试方法

如果你提交后发现有样例不过，先别急着看别人的代码。我常用的方法是：自己构造一个 3x3 的小矩阵，手工算出所有 s[i][j]，然后跟程序打印出来的 s 对比。只要 s 对了，查询公式几乎不可能错；如果 s 不对，就一行行检查循环边界和递推式。

比如下面这个 3x3 矩阵：

它的 s[1][3] 应该是 6，s[2][3] 应该是 21，s[3][3] 应该是 45。你可以在代码里临时加一行 printf 把 s 打出来，跟手算结果对比。这种“手工小样例验证法”虽然笨，但真的能帮你把公式、下标、边界问题一次性暴露干净。

5. 这个模板还能延伸到哪里

5.1 二维差分的逆向操作

学会二维前缀和之后，二维差分几乎是白送的。差分是前缀和的逆运算：如果要在 (x1, y1) 到 (x2, y2) 的矩形区域整体加上一个值 v，我们可以维护一个差分数组 d，然后做四次修改：

text复制d[x1][y1] += v
d[x2 + 1][y1] -= v
d[x1][y2 + 1] -= v
d[x2 + 1][y2 + 1] += v

最后对整个差分数组做一遍二维前缀和，得到的就是每个位置最终被加了多少。这里加减号的规律和查询公式完全一致。很多“对一个棋盘做若干次矩形区域累加”的题目，本质就是在用二维差分加二维前缀和。所以你现在花的功夫，后面会反复赚回来。

5.2 面试和竞赛里的实际地位

二维前缀和属于基础模板中的基础。面试中遇到矩阵区域求和的题，第一反应基本就是二维前缀和；图像处理里的积分图（integral image）也是同一套数学原理，只是换了个工程化的名字。竞赛里它很少单独作为压轴题，但经常作为大型问题的前置步骤：先跑一次二维前缀和，让后续所有查询都变成 O(1)，主算法的时间复杂度一下子就降下来了。

所以说到底，吃透这一题，不只是在背一个模板，而是在训练一种“把重复计算提前做好”的预处理思维。这个思维后面还会用在很多地方。

5.3 想再进一步可以练什么

如果你已经能独立 AC 这道题，我建议按照这条线往下走：一维差分、二维差分、最大子矩阵和、二维树状数组。其中最大子矩阵和会用到二维前缀和作为辅助工具，但核心是枚举上下边界并结合一维逻辑去优化复杂度；二维树状数组则是处理“带修改的二维前缀和”，属于另一个层级的知识点。

练习顺序上，先把二维差分做熟练，再碰动态修改的场景，不要一口气吃太多。每学一个新的模板，都像这篇文章里说的那样，自己造一组小数据，手算一遍，再跑代码验证。等你能闭眼写出二维前缀和的建表与查询代码，后面很多二维题目对你来说都会轻松很多。

我在实际刷题过程中发现，最让我记忆深刻的不是哪道题多么难，而是某个模板第一次真正理解透的时刻。子矩阵的和这道题就是这样的节点：一旦你亲手画过容斥推导，亲手写出一份一遍过的代码，你就再也不会怕这类“查询一个区域”的问题。下一步，大胆去碰二维差分吧，你已经站在门槛上了。