刷题圈里聊到“洛谷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) 被多少张地毯覆盖过。例子里如果 n5然后来了三张地毯最终输出的矩阵里某些格子是 3某些是 0这就是题目要求的“覆盖次数”。理解题意时有一点需要特别注意这里说的格子坐标不是数学坐标系里的连续点而是离散的网格坐标一张地毯铺下去矩形边界包含的格子全部都会 1。这个“离散网格 矩形范围修改 最终单点输出”的模型几乎是二维差分所有题目的标准模板。1.2 为什么第一反应暴力会翻车很多新手看到这题的第一反应是开一个二维数组每读入一张地毯就写个双重循环把 x1 到 x2、y1 到 y2 之间的格子全部加 1。逻辑上完全正确代码也能跑出正确答案问题只在于复杂度。最坏情况下每次地毯覆盖整个网格也就是 n×n 个格子要各自加一次m 张地毯就是 O(m·n²)。题目数据范围 n 最大可以到 1000m 最大可以到 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] vd[r1] - v。为什么这两步就够了因为差分数组 d[i] 在还原时要用前缀和累加b[i] b[i-1] d[i]还原出来的 b 才是原数组 a 上被多次修改后的最终结果。在 l 位置加 v 之后从 l 开始一直到数组末尾前缀和都会多出 v在 r1 位置减 v前缀和走到 r1 时又会少掉 v于是 v 的“影响范围”就恰好被限制在 [l, r] 之间。你可以把它理解成一种延迟标记技术不是每次修改都立刻落到原数组上而是先把“影响”记录在起点和终点最后用前缀和统一结算。一维差分本质上是原数组的“导数”前缀和则是它的“积分”两者互为逆运算。2.2 二维差分的四个标记点一维差分的区间只需要处理左端点和右端点后面一格但二维差分的矩形区域需要考虑四个方向的变化。假设要对以 (x1, y1) 为左上角、(x2, y2) 为右下角的矩形内部全部 v二维差分数组 d 需要做这样四次修改d[x1][y1] vd[x21][y1] - vd[x1][y21] - vd[x21][y21] v看到这个结构很多人第一反应是“四个角各搞一下”但更进一步理解会更好一维差分是“左端点加、右端点后一个减”二维差分可以看作对 x 和 y 两个方向分别做差分。上面四个操作可以拆成两步来看——先把 y1 到 y2 这一行的区间加操作拆成 d[x1][y1] v 和 d[x1][y21] - v再把 x1 到 x2 沿行方向的区间加操作也拆出来组合之后自然就多出了 x21 行的两个对称标记。最终还原的核心公式是二维前缀和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] 1d[4][2] - 1因为 x21 4d[2][4] - 1因为 y21 4d[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而标记时会出现 x21 等于 1001 的越界情况所以必须多留几格。有同学只开 1001结果在 n1000、x21000 时d[1001] 直接数组越界本地可能不报错交上去就疯狂 RE这个坑我见过太多次。第二是输入输出我用了 scanf/printf 而不是 cin/cout因为老评测机对 iostream 的兼容性没想象中好虽然 n、m 不算特别大但养成“大数据用快读快写”的习惯总是没错的。3.2 Java 实现要点Java 选手写这道题时核心逻辑完全一样但有几个 JVM 特有的注意点。首先是数组申请int[n2][n2] 是比较稳妥的选择显式多留两行两列避免标记 x21 或 y21 时越界。然后是读入直接用 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 都触发一次系统调用。当 n1000 时输出内容大约有 100 万个数用 print 逐次输出会非常慢攒成字符串再一次性输出是目前 Java 题解里的常规优化手段。3.3 时空复杂度与数据范围考量二维差分的复杂度非常好算每次矩形修改只做四次数组操作所以 m 次修改是 O(m)最后遍历一遍 n×n 矩阵做前缀和还原是 O(n²)。总时间复杂度 O(n² m)。空间上只需要一个 (n2)×(n2) 的 int 数组大约 4MB 左右在题目常见的内存限制 125MB 下非常宽裕。对比一下暴力解法的时间消耗我实际测试过n1000、m10000 的随机数据暴力双重循环在本地大概要跑 10 到 20 秒而差分写法基本是 0.01 秒以内完成。这就是算法题里“先分析复杂度再动手”的意义所在。当你看到题面里的数据范围是 10³ 到 10⁴ 的时候就应该立刻反应到O(n²) 的算法可行O(m·n²) 的算法不可行。这类“数据范围暗示算法”的直觉需要靠大量刷题才能建立。4. 常见错误、调试方法与经验技巧4.1 四个标记记混一个口诀搞定二维差分最常见的错误就是四个标记点方向写反。我一开始也总是记混后来总结出一个非常牢靠的口诀矩形加 v 时左上角加 v右上角右边一格减 v左下角下边一格减 v右下角右下那格加 v。翻译成代码就是x1, y1 位置加x1, y21 位置减x21, y1 位置减x21, y21 位置加如果你不想背口诀就回到原理想二维差分的本质是在一维差分基础上做了两轮展开。第一轮是列方向d[x1][y1] v 和 d[x21][y1] - v 负责让从第 x1 行开始的累加生效、到 x21 行结束第二轮是行方向每个列标记都要延伸到 y21 处做对称的减操作。把四个标记当成两组“一维差分区间的组合”比死记硬背靠谱得多。4.2 数组越界和输入下标这道题的坐标是从 1 开始编号的不是从 0 开始。很多从 C/C 基础题过来的同学习惯性把所有数组下标都从 0 开始写标记点时自然写成了 d[x1-1][y1-1] 之类的版本也能跑出部分正确答案但边界情况一多就会出错。我建议统一从 1 开始存储数组大小开 n2 或 n5让下标从 1 到 n 正常使用0 下标和 n1 下标留作缓冲区。这样四个标记点在 x21 直接指向第 n1 行时不会被判越界还原时 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 → 还原输出”三个步骤。比赛时这能帮你省下不少时间也让代码逻辑更清楚。这道题本身不难但它确实是进入二维差分世界最平滑的一块敲门砖把这个模型吃透后面很多难题都是它的变体。