椰程信奥·互动课件 专题6·前缀和与差分（二）
10:00 1 / 14
🧭 椰程信奥 · CSP复赛专题系列

专题6 · 二维前缀和与差分

把一维的「多退少补」推到平面上：
二维前缀和用容斥算出任意子矩阵的和，二维差分只改四个角就能刷完一整块矩形。
本讲用「地毯覆盖」与「激光炸弹」两道真题落地。

地毯覆盖（二维差分） 激光炸弹（二维前缀和） 容斥原理 / 四角改法
动机

为什么要推广到二维

一维做的是「一段区间」，二维要做的就是「一块矩形」——思路完全一样，只是加减的地方多了几处。

📏 一维

前缀和：s[i] = s[i-1] + a[i]

区间和：s[r] - s[l-1]（减 1 处）

区间加：b[l]+=x; b[r+1]-=x;（改 2 处）

🗺️ 二维

前缀和：S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j]

子矩阵和：加减 4 项（容斥）

矩形加：只改 4 个角

核心心法：一维「减 1 处」到了二维变成「减 3 处 + 补 1 处」，本质都是容斥原理——多算的减掉，多减的加回来。把一维彻底搞懂，二维只是多背两个公式。
3D🎲 二维前缀和 = 四块立体的容斥🖱 拖拽旋转 · 双击复位
为什么用 3D：二维容斥是最难讲清的一节。用四块可旋转的立体板叠加/挖切，「大 − 左 − 上 + 左上」就从公式变成了能动手拆的积木。
定义

S[i][j] 是以 (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]

S[i-1][j] 与 S[i][j-1] 两块重叠的部分正是 S[i-1][j-1]，它被加了两次，所以要减掉一次。

记忆法：「上加、左加、左上减、自己加」。

下标约定：一律 1-based，第 0 行第 0 列全为 0。这样 i=1 或 j=1 时 S[0][*] 天然为 0，不用写任何边界特判。
公式

求 (x1,y1) 到 (x2,y2) 的子矩阵和

sum = S[x2][y2]                       // 整块
    - S[x1-1][y2]                   // 减去上方多余
    - S[x2][y1-1]                   // 减去左方多余
    + S[x1-1][y1-1];                // 左上角被减两次，加回来

① 先取大块

从 (1,1) 到 (x2,y2) 的整块，肯定多算了目标以外的地方。

② 减上、减左

分别减去目标上方与左方的两块。

③ 补回左上角

左上角那一小块被减了两次，必须 +1 次补回来。

最高频错误：最后那个 + S[x1-1][y1-1] 忘了写，或写成减号。口诀：「减两加一」——减上、减左、加左上。
用 1×1 特例当场验证：令 x1=x2=1, y1=y2=1，公式变成 S[1][1] - S[0][1] - S[1][0] + S[0][0] = S[1][1] = a[1][1] ✓。如果你记的版本算不出 a[1][1]，那就记错了。
互动

二维前缀和 · 逐步构建与查询

查询
点击「下一步」，从 S[1][1] 开始一格一格把前缀和算出来。
核心

矩形区域加 1，只需要改 4 个角

要给 (x1,y1) 到 (x2,y2) 的整块矩形加 x：

d[x1]    [y1]     += x;      // 从左上角起「抬升」
d[x2+1]  [y1]     -= x;      // 过了下边界，横向抵消
d[x1]    [y2+1]   -= x;      // 过了右边界，纵向抵消
d[x2+1]  [y2+1]   += x;      // 右下角被抵消两次，加回来

🧠 和一维的对应关系

一维：b[l]+=x; b[r+1]-=x;（2 个点）。
二维：把「点」换成「角」，2×2 = 4 个角，符号同样遵循容斥。

⚡ 复杂度

单次矩形修改 O(1)，不管矩形多大。
最后统一做一次二维前缀和还原，O(n²)。

m 次修改总计 O(m + n²)，而暴力是 O(m·n²)。

数组要开多大：会用到 d[x2+1][y2+1]，而 x2、y2 最大为 n，所以至少开 (n+2) × (n+2)。这是二维差分最常见的越界点。
例题 1 / 地毯

地毯覆盖：二维差分的模板题

每张地毯盖一个矩形，问每个格子被盖了几层0111001210123211222101110两张地毯 → 重叠处盖了 2 层二维差分：只改四个角d[x1][y1] += 1d[x1][y2+1] −= 1d[x2+1][y1] −= 1d[x2+1][y2+1] += 1最后做一次二维前缀和还原。

n×n 网格，m 张地毯，每张覆盖一个矩形。问每个格子被覆盖几次。

🔍 建模

每张地毯 = 一次矩形 +1。
这正是二维差分唯一的用途场景：大量矩形修改，最后统一查询。

📋 三步流水线

  • ① 读入每张地毯，改 d 的 4 个角。
  • ② 对 d 做二维前缀和，还原成覆盖次数。
  • ③ 按 n 行 n 列输出。
样例核对：n=5, m=3，地毯 (2,2)-(3,3)、(3,3)-(5,5)、(1,2)-(1,4)。第 3 行第 3 列被前两张地毯同时覆盖 → 2。输出矩阵中间那个 2 就是它。
例题 1

地毯覆盖 · 代码走读

const int N=1005;
int d[N][N];                        // n≤1000，要多开两格
int main(){
  int n,m; cin>>n>>m;
  for(int i=0;i<m;i++){
    int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
    d[x1]  [y1]   += 1;
    d[x2+1][y1]   -= 1;
    d[x1]  [y2+1] -= 1;
    d[x2+1][y2+1] += 1;              // 右下角补回
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];
      cout << d[i][j] << (j==n?'\n':' ');
    }
  }
  return 0;
}
三个坑：① 数组开 N=1005 而不是 1000（要用 x2+1、y2+1）；② d[x2+1][y2+1] 是 +=1 不是 −=1，符号写反结果会整体错位；③ 输出行末不能有空格，用 (j==n?'\n':' ') 控制。
例题 2 / HNOI2003

激光炸弹：二维前缀和 + 枚举正方形

N 个带价值的点，一颗炸弹摧毁边长为 R 的正方形内所有目标，求最大总价值。

① 坐标平移

点的坐标从 0 开始，先 整体 +1 转成 1-based，避免下标 0 越界。

② 价值累加

同一坐标可能有多个点，用 s[x+1][y+1] += v 累加而不是赋值。

③ R 要截断

R 可能极大（甚至 10⁹）。地图最大边长为 5001，所以 R = min(R, 5001)。

为什么 R 必须截断：地图实际范围只有 1…5001。若 R 更大，公式里 s[i-R][j] 的 i-R 会变成很大的负数，直接数组越界——这是本题最隐蔽的 RE 点。
题目给的是 0 ≤ x, y < 5001，即坐标最大 5000。转 1-based 后最大 5001。所以地图边长就是 5001，扫描上界取 5001、R 截断到 5001。别想当然写成 5000 或 n。
例题 2

激光炸弹 · 代码走读

const int M=5001;
int s[M+2][M+2];                     // 约 100MB，注意内存
int main(){
  int N,R; cin>>N>>R;
  if(R>M) R=M;                       // ★ 截断，防越界
  for(int i=0;i<N;i++){
    int x,y,v; cin>>x>>y>>v;
    s[x+1][y+1] += v;                // ★ +1 平移 + 累加
  }
  for(int i=1;i<=M;i++)
    for(int j=1;j<=M;j++)
      s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
  int ans=0;
  for(int i=R;i<=M;i++)
    for(int j=R;j<=M;j++)
      ans = max(ans, s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);
  cout << ans << "\n";
}
三个坑：① 枚举起点是 i=R 而不是 1（否则 i−R < 0 越界）；② 数组必须开在全局（约 100MB，放 main 里会爆栈）；③ ios::sync_with_stdio(false) 记得加，否则 25M 次循环 + 输入输出容易超时。
诊断

二维专题高频易错辨析

① 二维前缀和的构建公式里，为什么要减 S[i-1][j-1]？

② 矩形 (x1,y1)~(x2,y2) 加 1，右下角 d[x2+1][y2+1] 应该？

③ 激光炸弹里 R 远大于地图边长时应当？

拿分

一道题 100 分是分档给的——不会正解也要先拿保底

复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。

第 1 档 特判 5~10 分 约 2 分钟 第 2 档 暴力 20~30 分 约 8 分钟 第 3 档 特殊性质 40~60 分 约 15 分钟 第 4 档 正解 100 分 约 25 分钟

① 特判档：先别想算法，看数据范围表

题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行， 就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。

② 暴力档：按题意最直白地写一遍

多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。

③ 特殊性质档：题目里那句「若……」

常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。

④ 正解档：思路定了，就赢了八成

考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。

考场纪律：每档设时间上限，到点还没调通就 立刻提交当前版本，保住已有分数，再往上冲。最常见的翻车是"正解写了 50 分钟没过，连暴力分都没交上去"。
拿分

本讲 2 道题，各自的四档怎么走

地毯（二维差分） · CARPET

第1档 · 2 分钟
n == 1 → 只有那一个矩形是 1

第2档 · 8 分钟
每张地毯逐格 +1，n ≤ 1000、区域 ≤ 1000² 稳过

第3档 · 10 分钟
所有地毯都是 1×1 → 就是二维计数，不用差分

第4档 · 15 分钟
四角 d[x1][y1]+=1, d[x1][y2+1]−=1, d[x2+1][y1]−=1, d[x2+1][y2+1]+=1 再二维前缀和

激光炸弹 · LASER

第1档 · 2 分钟
R == 1 → 就是单格最大值；目标点全在 R 内 → 直接输出总和

第2档 · 8 分钟
枚举每个格子为左下角逐格求和，R ≤ 10、坐标 ≤ 5000 稳过

第3档 · 10 分钟
R 覆盖整个区域 → 直接输出总和

第4档 · 15 分钟
二维前缀和 + O(1) 查询每个 R×R 子矩阵，取 max

50 分钟时间盒（一题的节奏）：
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查 freopen 与文件名。
课堂上别让学生"从头想正解"。先要求每个人 15 分钟内交出第 1、2 档， 再放开冲正解。这个顺序一换，平均分通常能涨一大截——因为它杜绝了"想了 40 分钟，交上去 0 分"。
小结

本讲知识树与自检清单

🌳 知识树

二维前缀和：S[i][j] = 上 + 左 − 左上 + 自己；子矩阵和 = 大 − 上 − 左 + 左上。

二维差分：矩形加只改 4 个角（右下角加回）。

流水线：差分改四角 → 二维前缀和还原 → 输出/取答案。

✅ 考场 N 步自检

  • 下标从 1 开始了吗？坐标含 0 就整体 +1 了吗？
  • 容斥符号对吗？记住「减两加一」。
  • 数组开够 n+2 / M+2 了吗？
  • 大数组是不是放在全局？（放 main 会爆栈）
  • 范围参数（如 R）有没有截断到地图尺寸内？
  • 值会不会超 int？叠加次数多时要考虑范围。
下机前：默写两个模板——地毯（四角改法）与激光炸弹（min 截断 + 枚举右下角）。能默写 ≈ 本讲过关。

目录