中 · 前缀和

二维区间求和

一维的技巧是一次减法。到了二维，每个前缀都是矩形，于是求子矩形要减掉两条边条、再加回被减了两次的那个角 —— 一张手画图比公式管用。

一句话答案构造 <code>P[i][j]</code> = 前 i 行、前 j 列的总和；任意矩形 (r1,c1,r2,c2) 的和就是 <code>P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]</code>。

题目

输入: 第一行是 n、m、q（1 ≤ n, m ≤ 50，1 ≤ q ≤ 100）。接下来 n 行、每行 m 个整数（0 ≤ a ≤ 1000）。然后 q 行：r1 c1 r2 c2（1 ≤ r1 ≤ r2 ≤ n，1 ≤ c1 ≤ c2 ≤ m）。

输出: q 行：每个查询输出该矩形的和，一行一个。

样例:

输入输出
2 2 3
1 2
3 4
1 1 2 2
1 1 1 1
2 2 2 2		10
1
4

先说行、再说列 —— 和 矩阵求和 同一套约定。单个格子（r1 = r2、c1 = c2）也是合法矩形，整张网格也是。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 给表格垫一圈零

声明 P[55][55]，让第 0 行和第 0 列保持为零。于是构造式 P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + a[i][j] 在 i = 1、j = 1 时也直接成立，不用任何特判 —— 和一维版本变干净的是同一个技巧。

提示 2 — 把四个角画出来

背查询公式之前，先画两个矩形：大前缀 (1,1)-(r2,c2) 和目标 (r1,c1)-(r2,c2)。要减掉的两条边条在上方和左方，而它们在左上角重叠 —— 减掉两条，把那个角加回来一次。见过这张图，公式就不再是咒语。

提示 3 — 查询公式和构造公式是同一张图

构造和查询是同一张图的两个读法：构造是往三个前缀里加一个格子；查询是从大前缀里减边条。如果构造过了样例而查询挂了，bug 几乎总在查询那行的角上符号，而不是构造。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int P[55][55];

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    for (int j = 0; j <= m; j++) P[0][j] = 0;
    for (int i = 0; i <= n; i++) P[i][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + a;
        }
    }

    for (int k = 0; k < q; k++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1] << endl;
    }
    return 0;
}

「付一次答多次」的二维版到手了：一维原型在 区间求和，这套四角容斥以后在网格计数问题里还会回来。两版共享的教训：先把查询隐含的结构预处理出来，再让每个问题变便宜。

深度解析

为什么这样做对

把 P[i][j] 定义成「前 i 行、前 j 列的总和」。任意矩形就用容斥拆:大前缀减上面的边条、减左边的边条,再加回被减了两次的左上角。构造和查询是同一张图的正反两个读法。

代价

构造 O(n·m),每次查询 O(1),空间 O(n·m)。逐个矩形暴力加是每次查询 O(n·m) —— 50×50 网格、q = 100 时,是 25 万次加法对 100 次减法的差距。

常见错法

  • 查询里忘了 + P[i-1][j-1] —— 左上角被减了两次,必须加回一次。碰到第 1 行或第 1 列的查询测不出这个 bug(那些边条是零)。
  • 构造时在原数组上就地复用:读进同一个二维数组再 P[i][j] += a 可以,但下标差一(a[i][j] 与 P[i-1][j-1] 混用)是典型的无声腐蚀。
  • 行列顺序:题面是「先 n 行、每行 m 个」。在正方形样例上换过来碰巧没错,矩形测试一上就挂。

下一步

一维原型是 区间求和 —— 两题对照着读,容斥就一目了然。网格的下一站是二维差分(修改 + 查询同时要)。

记住这两句

  • P[i][j] = 前 i 行前 j 列;矩形 = 大 − 上 − 左 + 角。
  • 第 0 行、第 0 列垫零,所有公式都不再需要特判。
🐞 这段是错的 —— 点开,亲手让它挂一次

把左上角弄丢了 —— 那个角被减了两次,从来没加回来

#include <iostream>
using namespace std;

int P[55][55];

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int j = 0; j <= m; j++) P[0][j] = 0;
    for (int i = 0; i <= n; i++) P[i][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + a;
        }
    }
    for (int k = 0; k < q; k++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] << endl;  // bug: no + corner
    }
    return 0;
}