1. 从一个填数游戏说起为什么矩阵操作会卡住你如果你刷过算法题或者做过图像处理十有八九碰过这类需求给一个二维矩阵把某个子矩形区域的所有数统一加上一个值连续做几百上千次最后问你某个位置的值是多少。最直白的做法就是每次遍历这个子区域逐格加值简单归简单可一旦矩阵是1000乘1000操作一万次算下来就是十亿次级别的操作在要求严格的时间限制下基本就挂了。二维差分就是专门用来解决这类“区间批量操作”问题的工具。它跟一维差分一脉相承核心是同一个思路把区间上的批量修改由逐元素操作改成端点操作最后用一次前缀和把结果恢复出来。这样无论你做了多少次区间修改真正落到矩阵上的循环次数只跟矩阵本身大小有关跟操作次数无关复杂度直接从“操作数×面积”降到了“操作数面积”量级上完全是两个世界。这篇文章适合所有刷题选手、做图像预处理的朋友以及任何被批量矩阵加减折磨过的同学。我会先快速带过一维差分因为它算二维差分的“前置技能”然后重点展开二维差分的构造、代码实现、常见应用和踩坑记录。全程用最直白的语言讲保证你读完能直接上手写代码。如果你对差分还没概念建议先找一个一维差分的题做几道再来看二维。不过即便你完全没接触过只要懂最基础的循环和数组也完全能跟上下面的思路。2. 前置技能一维差分到底在做什么2.1 从“逐个数加”到“端点标记”先回忆一下一维差分。假设你有一个长度为n的数组a初始全是0现在要执行m次操作每次把[l, r]区间内的每个元素加上v最后输出整个数组。暴力做法很好理解每次操作时循环i从l到r依次加v。m次操作下来时间消耗是m乘以平均区间长度如果n和m都是10的5次方这就是100亿次操作完全没法接受。差分数组的思路是这样的构造一个b数组长度n2初始为0每次区间加操作改为b[l] vb[r1] - v做完所有操作后对b从1到n求前缀和即 a[i] a[i-1] b[i]这里前缀和就是累加b数组得到的a就是最终结果。为什么这么改因为b数组记录了“增量”的变化趋势。在位置l突然多了v的增量所以往前累积时到l这里总和会跳增v在r1这个位置增量又减掉v于是累积总和在r1处归回原值。这样一次区间修改就变成了两次单点操作。2.2 一维差分的还原本质还原过程特别容易理解你现在拿到的b数组是“变化率”而前缀和就是把它积分回原函数。对b做一次从左到右的累加每个位置得到的结果就是经过所有修改后该位置的最终值。这种做法的精髓在于修改是O(1)的还原是O(n)的总复杂度只跟操作次数和数组长度相关而非操作次数乘以区间长度。一维差分和一维前缀和是一对互逆操作差分数组还原后是原数组前缀和数组差分回去也是原数组。搞明白了这个二维差分其实就是把“区间端点”的概念扩展到“矩形四个顶点”思想完全一致只是从两条线变成四个点收拾起来稍微复杂一点。3. 二维差分的核心思路用四个点代替一个矩形3.1 差分数组的定义与还原方式现在我们讨论二维场景。假设有一个n行m列的矩阵a初始元素都是0。我们要支持的操作是把左上角为(x1, y1)、右下角为(x2, y2)的子矩形内的所有元素加上v执行若干次后输出整个矩阵。暴力做法的代价显然也是“操作次数×矩形面积”在矩阵和操作量都大的时候直接爆炸。二维差分构造一个同样尺寸或者略大一圈的辅助数组d思路是把“在一个子矩形内均匀增加v”这个操作转化为在差分数组四个特定位置上的单点修改然后对差分数组横向、纵向各做一次前缀和就还原出原矩阵。具体来说每次矩形加v操作需要四步d[x1][y1] vd[x1][y21] - vd[x21][y1] - vd[x21][y21] v做完所有操作后对d按照“先横向累加再纵向累加”或者反过来的方式做二维前缀和得到的新矩阵就是最终每个位置的值。3.2 为什么是四个点而不是两个这就要说到一维和二维的本质差异。一维区间只有两个端点起点和终点所以我们只需要在起点加、终点后的位置减。但二维矩形的“边界”有四条左、右、上、下。你需要在左上角位置“开启”增量在右上角的右侧“关闭”横向上的增量在左下角的下面“关闭”纵向上的增量而右下角的右下位置因为横向纵向都被减了一次会多减一次所以要再加回来保平衡。为了看得更直观我们假想一个例子一个3行4列的矩阵初始全0执行一次“从(1,1)到(2,3)的矩形加5”操作。直接写代码模拟一次然后再看看差分数组d是什么样子位置0123400000010500-520000030-5005d数组只在四个位置有非零值(1,1) 5(1,4) -5(3,1) -5(3,4) 5。现在对d做二维前缀和每个位置等于它上方和左侧的累计贡献你可以手动推一推最终得到的矩阵就是除了(1,1)到(2,3)区域内是5、其他位置都是0。这个例子我认为对理解帮助极大强烈建议拿纸笔画一下。3.3 二维前缀和公式的由来如果你熟悉二维前缀和那你还记得求子矩阵和的公式是sum(x1, y1, x2, y2) S(x2, y2) - S(x1-1, y2) - S(x2, y1-1) S(x1-1, y1-1)二维差分的四个修改点本质上就是这个公式的“逆向”使用。你对差分数组的某个位置修改1等效于对最终矩阵的“某个前缀区域”整体加1。所以当你需要“矩形区域加v”时你在预处理前缀和时经历的四个方向上都做相应调整。这是理解二维差分最关键的一层你把修改操作放到差分数组上还原操作就是求二维前缀和而二维前缀和的公式天然包含了加减交错项所以要四个点配合。你要是背公式容易串就记住一条每次操作改左上角、右上角右一列、左下角下一行、右下角右下角四个点分别是 、-、-、。这里有个重要的边界问题如果你的矩阵从下标1开始编号这在竞赛里几乎是约定俗成的那么d的尺寸应该是(n2)×(m2)因为操作中会出现y21、x21甚至这两个同时加1后的位置你必须预留出多一行多一列来存放这些边界修改。如果从0开始编号那要小心减到负下标这时候可以考虑整体偏移一位或者干脆在边界处单独判断。这个细节我放到后面的避坑部分细说。4. 完整代码实现一版能跑通的写法光讲原理不写代码等于耍流氓。我直接给一份C版本的二维差分实现后面再给一份Python版本。两份代码的输入输出约定完全一致方便你对照学习。4.1 C实现从构建到查询一次说清这里我采用最经典的流程读入原矩阵如果你想在已有矩阵基础上做叠加修改或者直接构造差分数组如果初始是全0。注意二维差分的构建有两种思路一种是初始矩阵全0操作时逐次调用修改函数另一种是已经有一个现成的初始矩阵这时候要把矩阵的每个位置通过“矩形加”操作插入到差分数组中。换句话说初始矩阵的第(i,j)位置相当于对矩形(i,j)到(i,j)加a[i][j]调用修改函数即可。这种处理方式非常统一代码会很简洁。#include bits/stdc.h using namespace std; const int MAXN 1005; long long d[MAXN][MAXN]; // 差分数组开大一格防止越界 void add(int x1, int y1, int x2, int y2, long long v) { d[x1][y1] v; d[x1][y2 1] - v; d[x2 1][y1] - v; d[x2 1][y2 1] v; } void buildPrefix(int n, int m) { for (int i 1; i n; i) { for (int j 1; j m; j) { d[i][j] d[i - 1][j] d[i][j - 1] - d[i - 1][j - 1]; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin n m q; // 如果输入中有初始矩阵可以先逐点拿add加进差分数组 for (int i 1; i n; i) { for (int j 1; j m; j) { long long x; cin x; add(i, j, i, j, x); // 单点加本质上就是1x1矩形加法 } } while (q--) { int x1, y1, x2, y2; long long v; cin x1 y1 x2 y2 v; add(x1, y1, x2, y2, v); } buildPrefix(n, m); for (int i 1; i n; i) { for (int j 1; j m; j) { cout d[i][j] \n[j m]; // 末行位置换行 } } return 0; }代码核心就是add函数里的四次修改和buildPrefix里的二维前缀和还原。你注意buildPrefix里那行d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]这其实就是二维前缀和的标准递推只不过这里直接把d数组本身变成了最终矩阵。读这段代码的时候脑子里过一遍d[i][j] 最终等于“原来存放在d[i][j]的增量”加上“所有会影响到(i,j)位置的增量之和”而所有会对(i,j)产生影响的增量恰好是上方、左方、左上方这三个位置贡献的组合。4.2 Python实现清晰直白的对照版本Python版本特别适合自己跑着玩速度肯定比C慢但逻辑完全一致。如果你从事数据分析、图像处理相关工作可能对Python更熟悉照着写就能用。import sys def add(d, x1, y1, x2, y2, v): d[x1][y1] v d[x1][y2 1] - v d[x2 1][y1] - v d[x2 1][y2 1] v def build_prefix(d, n, m): for i in range(1, n 1): for j in range(1, m 1): d[i][j] d[i - 1][j] d[i][j - 1] - d[i - 1][j - 1] def main(): input_data sys.stdin.read().strip().split() it iter(input_data) n int(next(it)) m int(next(it)) q int(next(it)) size max(n 2, m 2) d [[0] * (size 1) for _ in range(size 1)] for i in range(1, n 1): for j in range(1, m 1): x int(next(it)) add(d, i, j, i, j, x) for _ in range(q): x1 int(next(it)); y1 int(next(it)) x2 int(next(it)); y2 int(next(it)) v int(next(it)) add(d, x1, y1, x2, y2, v) build_prefix(d, n, m) for i in range(1, n 1): print( .join(str(d[i][j]) for j in range(1, m 1))) if __name__ __main__: main()这段代码为了省事儿直接开了个正方形二维数组尺寸取行列中的大值实际使用时如果内存敏感可以精确开(n2)×(m2)。我在实际刷题时一般习惯精确开因为Python大列表很容易吃内存动不动几百兆就没了。4.3 复杂度对比从“不可接受”到“轻松秒杀”暴力做法的时间复杂度是O(q × 平均矩形面积)最坏情况下q次操作都是全矩阵那就是O(q·n·m)。二维差分的复杂度是每次操作O(1)最后还原O(n·m)总复杂度O(q n·m)。举一个具体场景。假设nm1000q100000暴力做就是100000×1000000 10的11次方次操作这在任何时间限制下都跑不完。而二维差分只需要10万次O(1)修改加一次100万规模的前缀和还原总体大约百万量级在普通PC上毫秒级跑完。这差距不是“快一点点”而是从“不能做”变成“随便做”。空间复杂度上差分数组比原数组多开一圈也就是多(n2)×(m2)的long long/int空间。这里吐槽一句千万别用int存累加值如果操作次数多、加的数值大二维前缀和还原的过程中中间值可能远超int范围出现溢出后整个结果直接乱掉。我当年就吃过这个亏刷题平台报了一个很离谱的答案排查半天才发现是int爆了。所以涉及累加一律long longCPython就不用操心这个但性能上要怎么做自己心里有数。5. 二维差分的经典应用场景5.1 图像区域的批量亮度调整图像处理里经常需要对一个矩形区域统一调整亮度或对比度这时候二维差分可以直接当“批量加亮”工具用。假设你有一张灰度图灰度值存在二维矩阵里现在要连续对几十个不规则的矩形区域加亮每个区域的增加量还不一样。如果你的第一反应是遍历每个区域逐像素修改那我建议你直接把这一节看完。思路是把图像矩阵当作初始矩阵每个矩形加亮操作就是一个add调用全部操作完成后做一次前缀和还原得到的就是最终亮度图。对于超大图像比如几千万像素的卫星图这个方案的性能优势极为明显。因为真正耗时的遍历只做一次而不是每个矩形都遍历一遍。这里要特别说明一点二维差分做的是“批量统一增加”如果你要对区域做加权调整比如中间加得多、边缘加得少那差分就帮不上忙了得用积分图、卷积或者其他方法。选工具前先搞清楚需求是均匀变化还是渐变变化这个判断能帮你少走很多弯路。5.2 差分结合二分的计数问题编程竞赛里有个很经典的套路在“最少染几次色能让目标区域达标”这类问题中用二分枚举尝试的次数然后借助二维差分快速判断当前次数下每个位置被覆盖了多少次。二分负责缩小答案范围差分负责每次O(1)修改、O(n·m)还原二者组合后的时间复杂度通常可以从O(答案×面积)降到O(log(答案)×(n·mq))。我拿一道典型的“矩形覆盖计数”题举例给定若干矩形操作每个操作是对一个子矩形加1问最终矩阵中值加起来大于等于K的单元格有多少。直接做法就是每次操作遍历所有格点复杂度是操作次数乘以矩阵面积用二维差分先O(q)完成所有修改再做一次O(n·m)前缀和还原最后一句if统计K以上的数量整个过程就像吃饭一样简单。这个组合在实际问题中出现频率非常高因为很多优化问题都可以转化为“覆盖计数判定”。学会了二维差分这类题的解题速度能提升一个明显档次。5.3 带权更新的数据统计再举一个更实际的场景一个学校有n×m个阶梯教室座位每场活动可能划出一块矩形区域来安排特定学生每个学生获得的活动积分不同。你有一长串活动计划最后要统计每个座位获得的总积分。这个场景的本质就是“多次矩形区域加权修改”用二维差分可以保证处理效率。这是二维差分的典型应用模式先批量记录修改再一次性结算结果。如果你的问题符合“大量区域更新 最后统计”这个特征二维差分就是首选方案。5.4 带坐标压缩的离散场景有些时候矩阵尺寸非常大比如坐标范围到10的9次方但实际涉及操作的区域数量却很少。这时候直接开数组肯定不行可以考虑坐标压缩把所有操作涉及的横纵坐标离散化映射到紧凑的整数区间再在这个压缩后的坐标系上使用二维差分。坐标压缩的实现步骤一般是收集所有操作涉及到的x1-1、x1、x2、x21以及y方向的同理排序去重然后用哈希映射到1到K的范围。注意一定要把你操作时会用到的所有关键坐标都包含进去尤其是差分修改时会触及的x21和y21否则还原时会漏掉边界。坐标压缩可以把一个尺寸巨大的稀疏矩阵变成紧凑的小矩阵再配合二维差分效率非常可观。6. 最容易踩的坑二维差分的实战避坑记录6.1 边界点加减顺序搞反我第一次学的时候老搞不清楚为什么是(x1, y1)、(x1, y21)-、(x21, y1)-、(x21, y21)背了几天还是容易混。后来我找到一个记忆锚点你写的是“左上加右上减左下减右下加”这四个点正好对应一个矩形的四个顶点的外扩位置。如果你自己推导一遍“在某个点1最终会扩散到哪些位置”这四步就再也忘不掉了。如果你实在记不住就用一个笨办法测试随便开一个小的矩阵自己手动加一个矩形然后做前缀和打印出来看看对不对。这样的情况我建议你动手推一次比背十遍公式都管用。6.2 数组越界开大一格是保命底线因为add函数里会出现y21、x21这样的下标如果矩阵下标最大到n和m那么d数组至少需要n2行、m2列才能装得下。有的同学图省事开成n1和m1结果一跑就数组越界轻则报错重则内存踩踏结果完全不可预测。这个问题的排查有时候非常头疼因为越界不一定每次都报错可能只有在特定数据下才崩。所以强烈建议开(n2)×(m2)或者干脆开MAXN×MAXN的全局数组稳当得多。6.3 初始矩阵的插入顺序与方式有些场景下矩阵初始不是全0而是已有确定数值。这时候你不应该直接把初始值写进a数组然后加差分而是要把每个初始元素也当作“一次矩形加操作”来插入差分数组。也就是对每个(i,j)调用add(i, j, i, j, a[i][j])。这么做的原因在于差分数组只负责记录“变化量”而初始矩阵本身就是“从0变到目标值的增量”把它们统一成add调用就不会在最终前缀和还原时出现重复累加或漏加的情况。如果你嫌这个方式太慢毕竟有n×m次add调用也可以直接在读入时按公式修改d数组效果一样。但如果想在代码里保持统一用add循环就完了反正复杂度还是O(n·m)没有额外开销。6.4 还原前缀和时弄错迭代方向二维前缀和的还原公式是d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]这个公式要求i和j都是从小往大遍历。如果你在第二个维度用从大到小的遍历那d[i][j-1]还没算好结果就完全错误。我在写代码时也犯过这种低级错误主要是一维前缀和的惯性——一维只要从左往右就行了二维纵向横向两个方向都必须保证“被依赖的位置已经更新过”。这个坑排查起来不算难只要测一个小矩阵就能发现但比赛的时候为了这个浪费几分钟确实不值得。6.5 内存与数值类型选择如果你用C写建议把所有差分数组都声明为long long不是int。原因前面提到了最终累加可能超过int最大值尤其是在多次加操作或大范围操作之后。另一个容易忽略的是输入输出性能数量级大时建议用快速IO比赛场景下cin/cout关了同步还可以但用scanf/printf更稳。Python用户要注意的是列表初始化时别误用乘法比如[[0](m2)](n2)这种写法会产生“共享同一行”的引用陷阱改一个值会把整列都改掉。要写成列表推导式[[0] * (m 2) for _ in range(n 2)]。这个坑非常隐蔽初学者很容易中招。6.6 常见问题速查表症状可能原因解决办法结果整体偏大初始矩阵被重复插入差分确认初始值只通过add插入一次不要既初始化又add结果整体偏小或全0前缀和遍历方向错误检查i/j循环是否为从小到大某些边界值不对数组开小了越界写坏内存d数组至少开(n2)×(m2)单个位置值异常大int溢出改用long longPython输出全是一行初始化用乘号导致行引用相同改用列表推导式初始化二维数组修改了区域外数值add四个点的符号或坐标写错用3×4小矩阵手动推一遍核对7. 题目练手建议与拓展思路想真正掌握二维差分不能光看不练。我建议按这个顺序来第一层找两道“裸题”——只要求实现矩形区间修改和最后输出矩阵的题目先保证你写的四种修改不会漏。这类题目一般在各大题库“差分”标签下都能找到例如AcWing里的“差分矩阵”题就很标准。第二层做几道与二维前缀和结合的题目比如“求多次矩形加后某个子矩阵的和”。这类题目本质上就是“二维差分还原后再做一次二维前缀和”是两套工具的组合。第三层挑战坐标压缩版本。例子是平面上给若干矩形操作坐标范围很大但矩形数量不多求最终每个区域被覆盖次数。这种题需要对坐标离散化非常熟练是对功底的综合检验。练完这些之后你再去看“差分进化算法”、“差分隐私算法”这些词里的“差分”会发现它们虽然都叫“差分”但内核并不是同一个东西。算法里的差分偏向“差值变化记录”进化算法里的差分是“用个体差做变异”隐私里的差分是“加噪声保护数据”。概念上容易产生混淆但实际完全是不同领域的命名习惯。我个人在实际操作中的体会是二维差分和很多基础算法一样看起来就那么几行代码但只有在一张草稿纸上把“四个点修改—前缀和还原”这个过程亲手推过一遍你才算真正入门了。后面再遇到“多矩形染色”“区域加权统计”这类问题脑子里就会立刻浮现出add函数那四行代码根本不用再翻笔记。