刷题圈里聊到“洛谷P3397 地毯”这道题，十个人里有九个都会提同一个考点：二维差分。作为差分思想从一维扩展到二维的经典入门题，它的题面非常朴素——一张 n×n 的网格上，连续铺 m 张矩形地毯，每铺一张就把它覆盖到的格子计一次数，最后输出每个格子被多少张地毯压住。可就是这么一道看起来“暴力遍历就能做”的题，却卡掉了一大批刚学算法的新手。这篇文章我打算把这道题从题意、数学原理、代码实现到实际踩坑一次讲透，适合正在学差分、前缀和，或者准备蓝桥杯、NOIP、程序设计竞赛入门的人看。
1. 题目在问什么：地毯覆盖计数问题
1.1 题意速读：n×n 网格上的连续覆盖
P3397 的输入格式很标准：第一行两个整数 n 和 m，表示网格大小为 n×n，共有 m 张地毯。接下来 m 行，每行四个整数 x1 y1 x2 y2，表示一张地毯覆盖从左上角 (x1, y1) 到右下角 (x2, y2) 的矩形区域。输出要求是 n 行，每行 n 个数，第 i 行第 j 列的数字表示格子 (i, j) 被多少张地毯覆盖过。
例子里如果 n=5，然后来了三张地毯，最终输出的矩阵里，某些格子是 3，某些是 0，这就是题目要求的“覆盖次数”。理解题意时有一点需要特别注意：这里说的格子坐标不是数学坐标系里的连续点，而是离散的网格坐标，一张地毯铺下去，矩形边界包含的格子全部都会 +1。这个“离散网格 + 矩形范围修改 + 最终单点输出”的模型，几乎是二维差分所有题目的标准模板。
1.2 为什么第一反应暴力会翻车
很多新手看到这题的第一反应是开一个二维数组，每读入一张地毯就写个双重循环，把 x1 到 x2、y1 到 y2 之间的格子全部加 1。逻辑上完全正确，代码也能跑出正确答案，问题只在于复杂度。最坏情况下每次地毯覆盖整个网格，也就是 n×n 个格子要各自加一次，m 张地毯就是 O(m·n²)。题目数据范围 n 最大可以到 1000，m 最大可以到 10000，乘起来就是 10000×1000000，一亿次操作起步，在洛谷的老评测机上很容易超时。
我见过不少同学在最开始学二维差分时思想没转过来，总想着“既然要改一块区域，那逐个改不是天经地义吗”。但在算法题的世界里，我们真正在乎的是“修改操作本身是否高效”。这里的地毯操作是典型的“区间整体加一个值，最后才查询”，它有个特点：修改次数 m 虽然多，但查询只在最后统一做一次。这种场景下，与其每次老老实实跑循环，不如先把所有修改“登记”在差分数组里，等全部处理完再用一次二维前缀和把结果算出来。这就是二维差分的核心思想——把对一块区域的修改从 O(n²) 降到 O(1)，但代价是最后必须花一次 O(n²) 还原。
2. 二维差分：给矩形批量“盖章”的工具
2.1 一维差分的回顾
在讲二维之前，咱先看一维差分。假设你有一组数 a[1] 到 a[n]，现在要执行多次操作，每次把区间 [l, r] 内的所有数同时加上 v。如果暴力循环，每次操作最长要加 n 个数，太慢。差分数组的做法是维护一个 d 数组，初始全 0。对于一次区间加操作，只需要做两件事：d[l] += v，d[r+1] -= v。
为什么这两步就够了？因为差分数组 d[i] 在还原时要用前缀和累加：b[i] = b[i-1] + d[i]，还原出来的 b 才是原数组 a 上被多次修改后的最终结果。在 l 位置加 v 之后，从 l 开始一直到数组末尾，前缀和都会多出 v；在 r+1 位置减 v，前缀和走到 r+1 时又会少掉 v，于是 v 的“影响范围”就恰好被限制在 [l, r] 之间。你可以把它理解成一种延迟标记技术：不是每次修改都立刻落到原数组上，而是先把“影响”记录在起点和终点，最后用前缀和统一结算。一维差分本质上是原数组的“导数”，前缀和则是它的“积分”，两者互为逆运算。
2.2 二维差分的四个标记点
一维差分的区间只需要处理左端点和右端点后面一格，但二维差分的矩形区域需要考虑四个方向的变化。假设要对以 (x1, y1) 为左上角、(x2, y2) 为右下角的矩形内部全部 +v，二维差分数组 d 需要做这样四次修改：
- d[x1][y1] += v
- d[x2+1][y1] -= v
- d[x1][y2+1] -= v
- d[x2+1][y2+1] += v
看到这个结构，很多人第一反应是“四个角各搞一下”，但更进一步理解会更好：一维差分是“左端点加、右端点后一个减”，二维差分可以看作对 x 和 y 两个方向分别做差分。上面四个操作可以拆成两步来看——先把 y1 到 y2 这一行的区间加操作拆成 d[x1][y1] += v 和 d[x1][y2+1] -= v，再把 x1 到 x2 沿行方向的区间加操作也拆出来，组合之后自然就多出了 x2+1 行的两个对称标记。
最终还原的核心公式是二维前缀和：
d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1]
这个公式出现时，很多人会问：为什么这儿不是 d[i][j] = ... 而是 += ？因为 d 数组里本身存的是“该点被差分标记累加后的值”，我们要把左上方向的所有标记影响都累加到自己身上，就得在原位做累加。容斥原理也好，积分还原也好，本质上就是在计算以 (i, j) 为右下角、以 (1, 1) 为左上角的矩形里所有差分标记对当前格子的综合影响。
2.3 用 3×3 小网格手推一遍
光看公式容易晕，我拿一个具体的 5×5 网格模拟一次。假设有张地毯覆盖 (2, 2) 到 (3, 3)，也就是第二行第三行的第二列第三列。四个标记点为：
- d[2][2] += 1
- d[4][2] -= 1，因为 x2+1 = 4
- d[2][4] -= 1，因为 y2+1 = 4
- d[4][4] += 1
你心里想着一个 5×5 矩阵，初始全 0，执行完这四个标记后，差分数组只在 (2,2)、(4,2)、(2,4)、(4,4) 四个位置有值：两个 +1，两个 -1。接着我们用二维前缀和从左到右、从上到下逐行还原。第一行全 0，因为 (1, ·) 没有标记。第二行从第一列开始累加，到第二列时 d[2][2] = 1，所以 (2,2) 变成 1；继续往右，到第三列时，d[2][3] = d[2][2] + d[1][3] + d[2][2] - d[1][2]？实际上第三列受到 (2,2) 标记的横向传递影响，依然为 1；走到第四列时，因为 d[2][4] 有个 -1，横向累加刚好把 1 抵消成 0。第三行同理，受纵向传递影响，第 2、3 列也是 1，第 1、4、5 列是 0。第四行从第 2 列开始，由于 d[4][2] 的 -1 和 d[4][4] 的 +1，整体依然为 0。你看，加加减减四个点，最后还原出来的矩阵里只有 (2,2) 到 (3,3) 是 1，其他地方全是 0。这就是二维差分的数学魔法：四个标记经过前缀和的传播，恰好形成一个矩形的“净覆盖区域”。
3. 完整代码与复杂度分析
3.1 C++ 参考实现
手推完原理，直接上代码。这道题我用 C++ 实现如下：
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; int n, m; int d[MAXN][MAXN]; int main() { scanf("%d%d", &n, &m); for (int k = 0; k < m; k++) { int x1, y1, x2, y2; scanf("%d%d%d%d", &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]; if (j > 1) printf(" "); printf("%d", d[i][j]); } printf("\n"); } return 0; }这里有两个关键细节要说清楚。第一是数组范围，我开的 MAXN = 1005，因为 n 最大 1000，而标记时会出现 x2+1 等于 1001 的越界情况，所以必须多留几格。有同学只开 1001，结果在 n=1000、x2=1000 时，d[1001] 直接数组越界，本地可能不报错，交上去就疯狂 RE，这个坑我见过太多次。第二是输入输出，我用了 scanf/printf 而不是 cin/cout，因为老评测机对 iostream 的兼容性没想象中好，虽然 n、m 不算特别大，但养成“大数据用快读快写”的习惯总是没错的。
3.2 Java 实现要点
Java 选手写这道题时，核心逻辑完全一样，但有几个 JVM 特有的注意点。首先是数组申请，int[n+2][n+2] 是比较稳妥的选择，显式多留两行两列，避免标记 x2+1 或 y2+1 时越界。然后是读入，直接用 Scanner 在数据量小的时候没问题，但如果你经常刷洛谷，建议换用 BufferedReader 加 StringTokenizer，或者 StreamTokenizer，读入速度会快一个档次。下面是我常用的写法：
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[][] d = new int[n + 2][n + 2]; for (int k = 0; k < m; k++) { st = new StringTokenizer(br.readLine()); int x1 = Integer.parseInt(st.nextToken()); int y1 = Integer.parseInt(st.nextToken()); int x2 = Integer.parseInt(st.nextToken()); int y2 = Integer.parseInt(st.nextToken()); d[x1][y1]++; d[x2 + 1][y1]--; d[x1][y2 + 1]--; d[x2 + 1][y2 + 1]++; } StringBuilder sb = new StringBuilder(); 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]; sb.append(d[i][j]).append(j == n ? '\n' : ' '); } } System.out.print(sb); } }这个版本里我用了 StringBuilder 收集输出，避免每次 print 都触发一次系统调用。当 n=1000 时，输出内容大约有 100 万个数，用 print 逐次输出会非常慢，攒成字符串再一次性输出，是目前 Java 题解里的常规优化手段。
3.3 时空复杂度与数据范围考量
二维差分的复杂度非常好算：每次矩形修改只做四次数组操作，所以 m 次修改是 O(m)；最后遍历一遍 n×n 矩阵做前缀和还原，是 O(n²)。总时间复杂度 O(n² + m)。空间上只需要一个 (n+2)×(n+2) 的 int 数组，大约 4MB 左右，在题目常见的内存限制 125MB 下非常宽裕。
对比一下暴力解法的时间消耗，我实际测试过：n=1000、m=10000 的随机数据，暴力双重循环在本地大概要跑 10 到 20 秒，而差分写法基本是 0.01 秒以内完成。这就是算法题里“先分析复杂度再动手”的意义所在。当你看到题面里的数据范围是 10³ 到 10⁴ 的时候，就应该立刻反应到，O(n²) 的算法可行，O(m·n²) 的算法不可行。这类“数据范围暗示算法”的直觉，需要靠大量刷题才能建立。
4. 常见错误、调试方法与经验技巧
4.1 四个标记记混？一个口诀搞定
二维差分最常见的错误就是四个标记点方向写反。我一开始也总是记混，后来总结出一个非常牢靠的口诀：矩形加 v 时，左上角加 v，右上角右边一格减 v，左下角下边一格减 v，右下角右下那格加 v。翻译成代码就是：
- x1, y1 位置加
- x1, y2+1 位置减
- x2+1, y1 位置减
- x2+1, y2+1 位置加
如果你不想背口诀，就回到原理想：二维差分的本质是在一维差分基础上做了两轮展开。第一轮是列方向，d[x1][y1] += v 和 d[x2+1][y1] -= v 负责让从第 x1 行开始的累加生效、到 x2+1 行结束；第二轮是行方向，每个列标记都要延伸到 y2+1 处做对称的减操作。把四个标记当成两组“一维差分区间的组合”，比死记硬背靠谱得多。
4.2 数组越界和输入下标
这道题的坐标是从 1 开始编号的，不是从 0 开始。很多从 C/C++ 基础题过来的同学，习惯性把所有数组下标都从 0 开始，写标记点时自然写成了 d[x1-1][y1-1] 之类的版本，也能跑出部分正确答案，但边界情况一多就会出错。我建议统一从 1 开始存储，数组大小开 n+2 或 n+5，让下标从 1 到 n 正常使用，0 下标和 n+1 下标留作缓冲区。这样四个标记点在 x2+1 直接指向第 n+1 行时不会被判越界，还原时 i 从 1 开始，d[i-1] 最多只访问到第 0 行，第 0 行保持全 0，正好让 1 行 1 列能正确累加。
还有一个细节：如果题面没有明说 x1 ≤ x2、y1 ≤ y2，最好在读入后做一次 min、max 交换，保证矩形输入合法。P3397 题面给定的是左上角和右下角，正常不会出现反向输入，但你在做其他二维差分题、尤其是遇到一些出题人故意搞事情的数据时，预处理 swap 一下会让代码鲁棒很多。
4.3 边界数据与多测坑
我曾经用自己写的二维差分模板去跑别的 OJ，结果 WA 了好几发，最后发现问题出在多组测试数据上。如果你拿到一题是多组输入，每次新用例都要把差分数组重置为 0，否则上一组数据留下的标记会污染下组答案。最省事的做法是用 memset(d, 0, sizeof(d)) 或 fill 函数整体清零，不要只重置被修改过的位置——因为还原后的 d 已经变成了前缀和结果，想精确找出哪个位置被改过反而麻烦。P3397 虽然只有单组数据，但保不齐你后面会碰见“二维差分 + 多组样例”的变种题，提前养成“每轮用例重置数组”的习惯，能帮你躲掉很多隐形坑。
另外一个边界细节是输出格式。洛谷要求每行行尾不要有多余空格，所以我代码里有 if (j > 1) printf(" ") 这样的处理。这个看起来很小的问题，曾经让我浪费过几次罚时，因为输出多余空格一般不会判 WA，但有些 OJ 的严格比对会判 presentation error。我做题时干脆把“输出每行末尾无空格”当成默认规范，无论题目有没有明确强调。
4.4 从 P3397 延伸出去的知识点
二维差分不是孤立的知识点，它和二维前缀和是一对互逆操作。如果你想快速求一个任意矩形的元素和，应该用二维前缀和：预处理 O(n²)，单次查询 O(1)。如果你想快速做矩形整体加减，最终才查询，用二维差分。如果修改和查询交替进行，那就不能用差分偷懒了，得用二维树状数组或线段树来支持在线操作。理解了这条“离线修改 vs 在线查询”的边界，你的算法视野才算是真正打开了。
另外，二维差分最常见的变形是“把坐标离散化后做矩形覆盖面积统计”。比如平面上有大量矩形，问哪些区域被覆盖了多次，这类题往往要先对 x、y 坐标离散化，再用差分标记每个离散格子的覆盖次数，最后把覆盖次数大于 0 的格子面积累加。原理和 P3397 一模一样，只是从逻辑坐标变成了物理坐标。还有一类题目会要求输出覆盖次数大于等于 k 的区域，或者在修改过程中动态输出某个格子的值，这些都是二维差分的进阶用法。
写在最后的小体会
P3397 这道题我前前后后帮人讲了不少于五次，每次讲解都有新人卡在同一个地方：总觉得自己理解了二维差分的公式，但一写代码就开始纠结四个标记点的正负号。我的建议是别急着背公式，先用 5×5 的小网格手推两三组数据，把“左上角加、两个边界外减、最右下角加”这个传播效果用笔画出箭头，画完再写代码，印象完全不一样。等你真正理解了二维差分的传播逻辑，之后再做矩形覆盖、区域染色、扫描线系列问题，都会顺畅很多。
说到最后的最后，分享一个小技巧：如果你不想每次标记都写四行 d 数组操作，可以封装一个函数，比如 addRect(x1, y1, x2, y2, v)，里面统一处理边界 swap 和四个标记点，主调代码就只剩下“读入地毯 → addRect → 还原输出”三个步骤。比赛时这能帮你省下不少时间，也让代码逻辑更清楚。这道题本身不难，但它确实是进入二维差分世界最平滑的一块敲门砖，把这个模型吃透，后面很多难题都是它的变体。
