如果你刚开始刷洛谷的算法题看到P3397这道题的名字叫“地毯”第一反应可能会觉得是要模拟一个铺地毯的过程或者处理某种覆盖问题。实际上它是二维差分最经典的模板题没有复杂的背景没有绕弯的细节题目就是给你一块 n*n 的地面铺 m 块矩形地毯问最后每块格子被多少块地毯盖着。我第一次做这题的时候还不知道二维差分这个概念直接模仿“铺地毯”的过程把每块地毯覆盖的区域里的每个格子都加 1结果交上去稳稳超时。后来才意识到P3397考的核心就是二维差分把每个子矩阵的“区间加一”操作从 O(面积) 优化到 O(1)最后统一还原。这篇文章我会从题目拆解、差分的原理、代码实现到真实踩坑和延伸应用完整地把这道题讲透。1. 题目拆解P3397到底在考什么1.1 题干里最容易被忽略的三个信息P3397的题意描述得很朴素读入 n 和 m表示有 n*n 的矩阵和 m 块地毯接下来 m 行每行给出 x1, y1, x2, y2代表一块地毯覆盖的是左上角为 (x1, y1)、右下角为 (x2, y2) 的子矩阵。要求输出最终的矩阵矩阵里每个元素表示当前位置被多少块地毯覆盖。很多新手做这道题时会忽略三个信息第一坐标是从 1 开始计数的不是从 0 开始第二数据范围是 n, m 都小于等于 1000第三题目只要求输出最后的结果中间过程完全不关心。这三个信息决定了正确的做法。如果忽略坐标从 1 开始这个细节后面实现差分会多出很多边界判断如果忽略数据范围就可能写出暴力模拟然后超时如果没看懂“只问最终结果”就想不到差分这种“先攒着、最后一起算”的离线做法。这道题位于洛谷的【算法2-1】前缀和与差分模块里题意干净利落数据范围也不大不小刚好卡在暴力能写但会超时的位置上非常适合用来理解二维差分。1.2 暴力写法为什么会超时先算一笔账。n 和 m 都在 1000 的规模暴力做法是用三重循环每读入一块地毯就把 (x1,y1) 到 (x2,y2) 这个矩形内部的每一个点都加 1。单块地毯最坏情况下覆盖整个矩阵也就是 1000×1000 10^6 个格子m 块地毯就是 10^6 × 1000 10^9 次操作。10^9 次加法在 C 里不是一个可以直接忽略的量级运行时间通常在 2 秒到 4 秒左右而洛谷单点时限通常只有 1 秒。即使你用快读、用 register 或者开 O2 优化也很难保证稳定通过。更关键的是这种暴力做法的时间复杂度是 O(n²m)最坏情况就是 10^9数据稍微刁钻一点就会超时。有的同学可能会想m 不是只有 1000 吗为什么朴素模拟过不了因为“m1000”不是瓶颈瓶颈在“每块地毯要遍历多少格子”。一块地毯可大可小最坏情况下一次就要更新 10^6 个点这个问题就出在“把修改落实到每一个格子”上。差分的思想恰恰是把“落实到每一个格子”变成“只修改几个标记点”最后统一计算这才把单次更新的复杂度从 O(面积) 降到 O(1)。1.3 核心考点提炼区间修改加上单点查询用算法术语概括 P3397 的要求就是四个字区间修改单点查询。区间是指每次操作的子矩阵修改是指对这个子矩阵整体加 1单点查询是指在最后需要知道每个坐标 (i, j) 到底被加了多少次。提到区间修改和单点查询熟悉前缀和、差分模型的人应该立刻有反应这种问题非常适合用差分来处理。差分的核心思路是“延迟计算”修改的时候不直接改原数组而是在差分数组上做标记当需要查询某个位置的值时再做一遍前缀和还原。这样把一件“一次性修改很多点”的事情拆成了“少量修改标记点 最后统一扫描”在算法竞赛里是一种非常典型的离线处理技巧。P3397 考的就是这个模型在二维世界里的版本。你如果能识别出“区间加最后单点查”这个特征相当于已经拿到了整道题的钥匙。接下来的问题就只剩一个二维差分到底怎么写。2. 二维差分原理四个下标搞定的O(1)修改2.1 先复习一维差分区间加法的O(1)小技巧二维差分是从一维差分扩展来的所以先把一维差分的逻辑理顺。假设有一个数组 a[1..n]我们要做 q 次操作每次把区间 [l, r] 内的所有元素加 v最后输出整个数组。朴素做法是每次遍历 l 到 r时间复杂度 O(q×区间长度)。用差分数组 d 的话每次操作只需要两步d[l] vd[r1] - v。全部操作完成后对 d 做一次前缀和也就是 a[i] a[i-1] d[i]就能还原出最终数组。为什么这样做是对的理解方式可以很直观d[l] 加 v会导致所有从 l 开始往后累加的位置都多出 vd[r1] 减 v又能让所有从 r1 开始往后累加的位置把这部分 v 抵消掉。于是最终效果就是只有 [l, r] 这一段受到了 v 的影响。一维差分之所以快正是因为它把“区间内每个点都加 v”的累加操作压缩成了“只在端点做两次修改”。一维差分的难点从来不是理解而是记住“修改在端点还原做前缀和”这个节奏。二维差分的难度在于从两个端点变成了四个端点但本质完全一样。2.2 二维差分的四个修改点对于二维数组假设我们有差分数组 cf当要对左上角 (x1,y1)、右下角 (x2,y2) 的子矩阵统一增加 v 时只需要做四个标记操作cf[x1][y1] vcf[x21][y1] - vcf[x1][y21] - vcf[x21][y21] v最后对 cf 做二维前缀和还原得到的就是每个位置被加过的总值。这里不需要对中间的格子做任何修改这就是二维差分能大幅降低时间复杂度的原因。四个点的位置有规律可循第一个点是被修改矩形的左上角加 v第二、三个点分别是矩形的下边界和右边界减 v第四个点是右下角的右下邻居加 v。很多人记不住第二个和第三个点到底该减哪个其实只要想明白一个道理矩形内部要被 v 影响而矩形外部的影响都要被消除四个标记点就是用来保证“内部 v外部抵消”的。还是拿 P3397 来说每次读入一块地毯就直接在这四个点做操作根本不需要去动子矩阵内部的任何元素。等 m 块地毯全部读完了再做一遍二维前缀和每个格子上覆盖的地毯数量自然就出来了。2.3 为什么不是三个点或者五个点容斥关系讲清楚我第一次学二维差分的时候最大的困惑是为什么一维是两个点二维变成四个点而不是三个点。后来发现用叠加和抵消的角度看就清楚了。假设我们只对 cf[x1][y1] 加 v那么做二维前缀和后所有满足 x≥x1 且 y≥y1 的位置都会额外多出 v。也就是说整个右下方向的直角区域都被影响了这显然超出了我们想要的矩形范围。我们需要想办法把多余的部分削掉。先做 cf[x21][y1] - v这一步会把所有 x≥x21 且 y≥y1 的位置的 v 都消掉相当于削掉矩形下方的一大块。再做 cf[x1][y21] - v这一步会把所有 x≥x1 且 y≥y21 的位置的 v 都消掉相当于削掉矩形右侧的一大块。这里你会发现下方和右侧被削掉的区域在右上角有一个重叠区也就是 x≥x21 且 y≥y21 的部分这个重叠区被减了两次结果反而多了 -v所以最后要在 cf[x21][y21] 加一次 v把它补回来。这个思路非常像集合的容斥原理加整体减两个部分再把被减重复的部分加回来。用这个逻辑去记四个标记点根本不需要死记硬背每次遇到情况都能自己推出来。2.4 为什么坐标到x21和y21数组要多开两格在二维差分的四个操作里第三个和第四个点用到了 x21、y21。当 x2 恰好等于 n 时x21 就等于 n1。如果数组只开了 n 的大小越界写入直接会导致运行时错误或者莫名奇妙地破坏邻接内存报出乱七八糟的错误。所以差分数组至少要开成 (n2)×(n2)甚至更稳妥地开成 MAXN×MAXN其中 MAXN 取题目约束里的最大值再加 5。很多人在 P3397 上第一次遇到段错误就是数组开小了这个 1 越界。这个问题在实现题里特别典型我们往往会按照 n 的大小开数组却忘记了差分标记点在右下角还要往后挪一格。记住二维差分数组永远比原数组大一圈这不是代码臃肿而是算法本身要求的空间余量。3. 实操从输入到AC的完整步骤3.1 数组规划与输入读取写代码前先把数组定下来。原题 n 最大 1000所以直接把差分数组开成 1005×1005 就足够了。我习惯开 MAXN 1005然后用全局变量这样数组自动初始化为 0省去手动 memset 的麻烦也不容易漏清零。读入方面直接用 cin 就行因为 n 和 m 只有 1000数据量不算大scanf 和 cin 在这个规模下没有明显区别。如果你只是为了这道题cin 加 ios::sync_with_stdio(false) 就够了没必要为了微小的差距破坏代码的可读性。读入的时候要注意坐标顺序。题目给的是 x1 y1 x2 y2代表的是从第 x1 行第 y1 列到第 x2 行第 y2 列的子矩阵。不要和那种“左上角、右下角”的表达搞混这里其实就是标准的行区间 [x1, x2] 和列区间 [y1, y2]直接对应差分操作里的四个点。3.2 完整AC代码C一共只需要30行直接给出能通过的参考答案代码短到超出很多人的预期#include bits/stdc.h using namespace std; const int MAXN 1005; int cf[MAXN][MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; while (m--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; cf[x1][y1]; cf[x2 1][y1]--; cf[x1][y2 1]--; cf[x2 1][y2 1]; } for (int i 1; i n; i) { for (int j 1; j n; j) { cf[i][j] cf[i - 1][j] cf[i][j - 1] - cf[i - 1][j - 1]; cout cf[i][j] (j n ? \n : ); } } return 0; }这段代码没有任何多余的逻辑每次读入地毯直接跑四个差分标记读完后在原来的 cf 数组上原地做二维前缀和还原边还原边输出。数组是全局变量默认全是 0所以不需要初始化。输出时注意 jn 时换行保持题目要求的 n 行 n 列格式。这里我想强调一点还原的时候直接在 cf 数组上操作而不是另开一个 sum 数组是完全可行的。因为二维前缀和的公式 cf[i][j] cf[i-1][j] cf[i][j-1] - cf[i-1][j-1]每次更新时用到的 cf[i-1][j]、cf[i][j-1] 都已经被更新成了前缀和形式而 cf[i-1][j-1] 也是前缀和所以原地更新不会产生冲突。这样可以省掉一个数组代码也更简洁。3.3 还原前缀和那行代码的为什么很多新手抄代码能过但被问到“为什么还原是 cf[i][j] ...”就答不上来。这一步其实就是二维前缀和的定义。我们定义原矩阵 a 是真实每个点的值差分矩阵 cf 是 a 的“二阶差分”那么 a 就等于对 cf 做二维前缀和。二维前缀和的递推公式是sum[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] a[i][j]。但在这里我们做的是“原地还原”所以公式变形为cf[i][j] cf[i][j] cf[i-1][j] cf[i][j-1] - cf[i-1][j-1]。写成代码就是那行累加。减掉 cf[i-1][j-1] 是因为 cf[i-1][j] 和 cf[i][j-1] 各自都包含了左上角区域一次加起来之后左上角被算了两次和二维前缀和公式里容斥的道理一模一样。如果你想直观验证可以手算一个 2×2 的小矩阵只做一次标记然后按行列推一遍很快就能看出每个格子的值是如何由四个标记点扩散出来的。3.4 时间复杂度和内存开销差分做法的时间复杂度分两部分读入并做修改的阶段每次操作 O(1)m 次就是 O(m)还原并输出的阶段需要遍历 n×n 个格子是 O(n²)。总体复杂度 O(n² m)。n 和 m 都取 1000 时总计算量约为 10^6 级别在 1 秒时限内非常稳。空间复杂度是 O(n²)因为我们需要存 n×n 的二维数组。在本题 1000 的规模下1005×1005 的 int 数组内存大约 4MB完全在洛谷空间限制之内。如果能用 short 之类的压缩理论上更省但在这种规模的题目里完全没必要老老实实用 int 就行。4. 真实踩坑P3397最容易翻车的几个细节4.1 下标从0开始导致的边界连环错我身边好几个朋友做这道题翻车不是因为差分公式不会而是因为读入后习惯性地把 x1、y1 减了 1让坐标变成从 0 开始。一旦从 0 开始差分数组的第一行和第一列就需要特殊处理因为不存在 x1-1 或者 y1-1 可以借用的位置。很多人在处理这个边界时容易漏判最后答案错得莫名其妙。建议的做法是题目说坐标从 1 开始就按从 1 开始写不要画蛇添足地改成 0 基。读入 x1 y1 x2 y2 之后直接用差分数组也从 1 开始存。循环输出的时候从 i1 到 nj1 到 n不需要关心第 0 行第 0 列发生了什么。这样做代码最干净也最不容易出错。有一种情况例外如果你确实习惯了 0 基下标那么在做差分标记时要小心四个点变成 x1,y1 / x21,y1 / x1,y21 / x21,y21其中 x21 和 y21 仍然可以等于 n所以数组的大小仍要开到 n2。同时还原的时候要从 0 开始循环。虽然可行但没有必要刷题图的就是稳尽量顺着题目的坐标体系走。4.2 前缀和还原公式写反的几种表现二维差分还原最经典的问题是把公式里的减号写错。常见的错误版本是 cf[i][j] cf[i-1][j] cf[i][j-1] cf[i-1][j-1]把容斥里的减法写成了加法。这个错误会导致矩阵里的数值变大而且越往右下角偏差越明显输出的结果像“糊了一层”一样。还有一个很容易犯的错是在循环里先更新了 cf[i][j]再用更新后的 cf[i][j] 去更新 cf[i][j1] 或 cf[i1][j]导致前缀和的扩散方向错误。正确做法是严格按照 i 从小到大、j 从小到大的顺序遍历每次只使用左、上、左上三个已经完成前缀和计算的格子。如果你发现输出的数值整体偏大优先检查是不是把减法写成加法如果你发现输出结果有规律地“从左上角扩散但方向不对”优先检查循环顺序和变量的更新顺序。这类错误一旦定位到位置基本一眼就能看出来。4.3 手算自测n5、m2的小样例为了验证自己的代码正确我在做这类题时总是会准备一个小规模样例。比如输入5 2 2 2 4 4 3 3 5 5第一块地毯覆盖 (2,2) 到 (4,4)第二块覆盖 (3,3) 到 (5,5)。按照题意手算最终的矩阵应该是0 0 0 0 0 0 1 1 1 0 0 1 2 2 1 0 1 2 2 1 0 0 1 1 1拿这个样例去跑你的二维差分代码输出的每一行如果和这个矩阵一样说明差分标记和前缀和还原逻辑基本没有问题。这里最值得注意的数字是 (3,3) 位置的 2它代表两块地毯交叉的地方这个值能把差分标记中的“加加减减抵消”情况完整地测出来。4.4 对拍脚本让暴力程序帮你查错手算样例只能覆盖一种情况如果想更稳妥地验证差分代码可以用对拍。思路非常简单写两份程序一份是朴素暴力直接三重循环模拟铺地毯的过程另一份就是你写的差分解法。用随机生成的小数据同时跑这两个程序比较它们的输出是否完全一致。对拍的小数据范围建议 n 取 1 到 10m 取 1 到 10坐标随机生成但保证 x1≤x2、y1≤y2。只要随机跑几十组如果输出全部一致差分代码的正确性就比较有保证了。你甚至可以在本地写一个批处理脚本循环生成数据、调用两个程序、比对输出但我个人经验是手写几组随机样例 一组手算样例已经足够对付 P3397 这个级别的题。真正容易出错的是比这复杂得多的应用场景所以先掌握手算自测的方法更实用。5. 从P3397向外走二维差分的延伸用法5.1 一类题都是这个模板涂色、覆盖、统计次数P3397 看起来是在铺地毯实际上很多题目都长着同一张脸。比如给一个二维网格有若干次操作每次给某个矩形区域“涂色”最后问每个格子被涂了几种颜色又比如一大片农田每次都用一个矩形杀虫剂喷洒某个区域最后统计每块地喷了几次再比如图像处理里的区域标记、游戏地图中的技能范围覆盖本质上都是在做同一件事区域整体加一最后查询每个点。这类题的关键识别特征就是“区间加、最后单点查”。只要你看到一个二维数组需要支持若干次矩形区域加某个数的操作并且所有操作都发生在最后查询之前第一反应就应该是二维差分。把 P3397 的 AC 代码吃透以后这类题的代码框架完全不需要改变换来换去无非是修改标记时加的值从 1 变成其他数字。5.2 二维差分与二维前缀和是互逆操作二维差分的还原过程用到了二维前缀和公式而二维前缀和本身也是竞赛里的基础考点。很多人会把它们混淆其实可以这么记一维差分是“区间加、最后前缀和还原”一维前缀和是“区间和、直接 O(1) 查询”二维差分是“矩形加、最后二维前缀和还原”二维前缀和是“矩形和、直接 O(1) 查询”。两套操作互为逆运算但又各自面向不同的问题类型。当你遇到“给一个静态矩阵多次询问某个子矩阵的元素和”这类问题时应该用二维前缀和而不是二维差分。判断标准很简单操作是“修改了再查”还是“一开始就给定、只查不改”。前者用差分后者用前缀和。P3397 之所以用差分而不是前缀和就是因为每个地毯相当于一次修改操作而且修改发生在查询之前。5.3 数据范围更大怎么办坐标压缩与扫描线如果你把 n 从 1000 扩大到 10^9二维差分直接开数组就行不通了因为空间不允许。这时候有两条路可以走一是坐标压缩把涉及的 x 坐标和 y 坐标离散化到可行规模然后依然使用差分思想只不过数组大小只跟操作涉及的行列数有关二是扫描线把矩形覆盖问题转化为一维差分的逐行或逐列处理用线段树或者树状数组来维护当前的覆盖层数。这些进阶做法的原理仍然建立在二维差分的“区间加、最后单点查”思想上。P3397 的价值就在于让你先把这个基础思想理解扎实之后无论扩展成离散化还是扫描线都能知道每一步修改是在干什么。从一个入门模板题延伸到高级数据结构算法的底层逻辑始终是相通的。5.4 学完这道题接下来可以练什么如果你把 P3397 的二维差分彻底弄明白了下一步可以去找几类相关的题来巩固。一类是“多次矩形加、最终输出矩阵”的同类题多刷几道熟悉模板一类是“一维差分 排序贪心”的组合题比如区间覆盖问题还有一类是“二维差分 二分答案”的题目把差分作为 check 函数里的一个工具。这些方向都能帮助你加深对“差分是延迟计算”这一核心思想的理解。就我个人经验来说P3397 最好的刷法不是只交一次 AC 就完事而是主动给自己加要求能不能不用看代码独立写出来能不能把四个标记点的位置给旁边的人讲明白能不能在 5 分钟内从读题到出代码这些练习比单纯刷题数更有价值。二维差分的代码很短短到很容易让人轻视它但真正决定成败的往往就是那四个角标对不对。这道题我前前后后写过很多遍几乎每次换一种实现方式都能发现一点以前没注意的细节。如果你也在这道题上卡过多花十分钟手算一次样例矩阵比反复看题解有效得多。把二维差分的“四个点”刻进肌肉记忆之后你会发现后面遇到矩形覆盖、网格加数的题目思路会通畅很多。