1. 为什么需要二维差分数组——从一维到二维的思维变化1.1 先复习一维差分别着急直接跳过来咱们先把一维差分彻底搞明白因为二维差分是一维差分的自然延伸一维没吃透二维就是个空中楼阁。假设你有一个长度为 n 的数组现在要执行 m 次操作每次都是把某个区间 [l, r] 内的所有元素同时加一个值 v。如果朴素地写每次都遍历 l 到 r操作复杂度是 O(n)m 次就是 O(nm)数据量一上来直接超时。这时候差分数组就上场了你先维护一个 diff 数组每次操作只改两个位置——diff[l] vdiff[r1] - v然后全部操作结束之后对 diff 做一次前缀和就能还原出最终数组。整个过程的复杂度从 O(nm) 降到了 O(nm)。一维差分为什么能用关键在于区间加这种操作它本质上是给一段连续区域打上统一的增量标记而前缀和可以把这个标记还原回每个位置原有的数值。差分数组天生就是为区间多次更新 最后统一查询这种场景准备的。1.2 一维到二维复杂度的问题瞬间放大现在场景升级了你面对的不再是一条线性的数组而是一个 n 行 m 列的二维矩阵。操作也升级了——每次把某个矩形区域比如左上角 (x1, y1) 到右下角 (x2, y2)内的所有元素同时加上一个值。如果你还是朴素地去双重循环更新每个格子一次操作的复杂度是 O(n*m)要是矩阵是 1000×1000操作来个 1000 次那就是 10^9 级别的计算量不超时才怪。二维差分要解决的就是把这个矩形区域批量更新的复杂度尽量压下去。它的核心思路和一维完全一致利用前缀和的逆运算来构造一个差分矩阵让每次矩形区域更新只修改 O(1) 个位置最后通过一次前缀和扫描还原整个矩阵。我在实际工程里遇到这种需求最常见的场景就是图像处理里的局部区域亮度调整还有游戏里地图上同时刷新多个区域的怪物或道具以及数据分析里给一张报表的多个子区域批量做加权。只要涉及矩形范围批量操作二维差分基本上是最快、最省事的方案。1.3 二维差分数组要解决的核心问题先明确一下我们要解决什么问题别把二维差分跟二维前缀和搞混了。二维前缀和解决的是离线快速查询子矩阵和而二维差分解决的是离线快速更新子矩阵。两者其实是镜像关系——前缀和适合多次查询、少量修改差分适合多次修改、最后统一查询。打个比方前缀和像是你把一整年的收支都记好了月底汇总一下各科目花了多少差分则像是你每天记账的时候只写今天餐厅200、交通50、其他-100到月底的时候再做一次汇总把每天的增量累积成每个科目的总支出。理解了定位之后二维差分的所有操作就都有了目标构建差分矩阵让每次矩形更新能用常数时间完成然后一遍前缀和还原出真实矩阵。接下来我直接给你讲透构造方法。2. 二维差分数组的构造原理——用面积视角拆解打标过程2.1 差分矩阵的构建思路不是猜出来的是从前缀和反推的很多教程上来就甩出二维差分的四行更新代码但我敢说大多数人看完是懵的——不知道为什么是这几个位置加加减减。这里我先不着急给代码而是从原理上把它推一遍。假定原矩阵是 a差分矩阵是 diff。二维前缀和的定义是sum[i][j] a[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1]。这个公式你应该熟——当前格子的前缀和等于当前值加上上方和左方的前缀和再减去左上方重复计算的部分。从前缀和还原差分其实就是把上面这个公式反过来用。对任意位置 (i, j)a[i][j] sum[i][j] - sum[i-1][j] - sum[i][j-1] sum[i-1][j-1]。如果你把 sum 换成 diff把 a 换成原矩阵的值这个关系依然成立。也就是说diff[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]。看到这里你可能会问这不就是差分数组的定义从一维搬到了二维吗确实如此。一维差分里 diff[i] a[i] - a[i-1]二维就是把行列两个方向的相邻差都考虑进去。所以构造差分矩阵的方法也很直接遍历原矩阵的每个格子按上面这个公式计算 diff[i][j] 就行。举个例子假设原矩阵是1 2 3 4 5 6 7 8 9按公式计算diff[1][1] 1左上角没有参考值diff[1][2] 2 - 1 1diff[2][1] 4 - 1 3diff[2][2] 5 - 2 - 4 1 0。算完整个 diff 矩阵之后你对它做一次二维前缀和扫描就能还原出原矩阵。这就是差分数组用前缀和还原的核心闭环。2.2 矩形更新的四个坐标点面积法一次看懂现在进入最关键的部分——如何用 O(1) 的时间完成一个矩形区域的加值操作。假设现在要把左上角 (x1, y1)、右下角 (x2, y2) 这个矩形内所有元素都加上 v。在一维情况下你只需要改两个点二维情况下需要改四个点。具体是diff[x1][y1] v diff[x1][y21] - v diff[x21][y1] - v diff[x21][y21] v光背下来不行我们来理解它为什么是这四个位置。你可以把 diff 的每一次更新看作是对最终前缀和结果做的一个面积修正。我们的目标是在 (x1, y1) 到 (x2, y2) 这个矩形内部每个位置在还原时都能多出 v矩形之外不能受影响。在 (x1, y1) 处加 v相当于从左上角开始把整个右下方向的区域都加上了 v影响范围是一个无限延伸的右下三角形区域。但这块区域太大了超出了目标矩形的宽度所以要在 (x1, y21) 处减 v把目标矩形右侧之外的部分砍掉。同理也要把目标矩形下侧之外的部分砍掉所以在 (x21, y1) 处减 v。但是右侧和下侧的减少区域在 (x21, y21) 处重叠了重叠的部分被减了两次所以要在那里加 v 补偿回来。你把这个过程在纸上画一下会发现四个点形成的加减模式正好把最终的影响范围限制在了目标矩形内。理解了这层面积逻辑再结合前缀和公式这四个点的来源就非常清晰了。2.3 为什么是 y21 而不是 y2边界地带的严谨推导很多初学者最容易问的一个问题是修改边界为什么不用 (x1, y2) 而用 (x1, y21)这其实涉及到前缀和的精确语义前缀和扫描到位置 (i, j) 时diff[i][j] 的累加会影响到包括 (i, j) 在内的所有右下方位置。如果我们要让第 y2 列还保留加值而第 y21 列之后不受影响那么减 v这个操作必须发生在 y21 列开头也就是下标 y21 的位置。放在 y2 位置的话连第 y2 列自己也被减掉了等于这个矩形右侧边界少了一列。同样的道理适用于 x21 行。这个细节在实战里特别容易出错——很多人写代码时随手就把 y21 写成了 y2结果查半天发现矩形右边那一列的值不对。说到底差分的边界更新一定是在目标区的下一个位置做抵消标记这是整个差分思想里最核心的约定。建议你动笔自己在草稿纸上画个 3×3 的小矩阵手动模拟一次前缀和还原过程比盯着屏幕看十行代码都有用。3. 核心代码实现与参数计算——从建表到还原一把梭3.1 差分矩阵的构建代码与下标约定先把代码框架搭起来。我这里统一从下标 1 开始存储原因很实际这样可以避免在边界处处理一堆 if 判断公式写起来也更干净。如果你非要从 0 开始也不是不行但每一处公式都需要特判边界代码可读性和出错概率都不如从 1 开始友好。n, m map(int, input().split()) a [[0] * (m 2) for _ in range(n 2)] diff [[0] * (m 2) for _ in range(n 2)] # 读入原始矩阵 for i in range(1, n 1): row list(map(int, input().split())) for j in range(1, m 1): a[i][j] row[j - 1] # 构建差分矩阵 for i in range(1, n 1): for j in range(1, m 1): diff[i][j] a[i][j] - a[i - 1][j] - a[i][j - 1] a[i - 1][j - 1]注意 diff 和 a 的尺寸我开了 m2 行、n2 列多出来的一圈是留给边界用的。比如当 x2 等于最后一行时x21 会落到 n1如果没有额外多开一列程序就会越界。多开一圈是写这类题和代码时最省心的习惯别扣那点空间。构建差分矩阵的本质就是对原始矩阵做一次离散二阶差分。你可以理解成把每个格子的值转换成了一个增量标记这些标记只有在做前缀和时才会被还原出来。构建过程的时间复杂度是 O(n*m)和矩阵本身的大小线性相关这是无法避免的也是整个流程里最耗时的部分之一。3.2 矩形更新的函数封装需要批量更新的时候直接写一个函数来打标记。这里把四个点的位置关系再次强调一下主方向加两次、反向减两次注意别把下标搞反了。def range_add(x1, y1, x2, y2, v): diff[x1][y1] v diff[x1][y2 1] - v diff[x2 1][y1] - v diff[x2 1][y2 1] v我见过不少人把这个函数封装的参数顺序搞乱调了老半天才发现给矩形对角线传反了。建议你统一到一个自己的固定习惯里第一个参数固定是左上角第二个参数固定是右下角别一会儿左上角一会儿左下角这种混乱最容易引入 bug。再说一次复杂度每次更新只改四个位置无论矩形多大复杂度都是 O(1)。这就是二维差分最爽的地方——你要处理一万个超大矩形区域的更新也只是修改四万个点配合最后一遍前缀和扫描整体复杂度就是 O(更新次数 矩阵面积)。3.3 前缀和还原出最终矩阵所有更新操作做完之后最关键的一步来了——把差分矩阵还原成最终矩阵。这里的还原公式就是二维前缀和的标准形式# 对 diff 做原地前缀和 for i in range(1, n 1): for j in range(1, m 1): diff[i][j] diff[i - 1][j] diff[i][j - 1] - diff[i - 1][j - 1]跑完这个循环之后diff[i][j] 的值就是原矩阵经过所有矩形更新之后的最终结果。因为前缀和是一个就地累加的过程所以不需要额外开数组直接在 diff 上操作就行。空间复杂度 O(nm)、时间复杂度 O(nm)这一步是线性扫描没有任何回旋余地但也是所有操作里最好优化和最容易理解的。3.4 复杂度分析为什么这套组合拳效率拉满把整个流程串起来看构建差分矩阵 O(nm)执行 k 次矩形更新 O(k)最后前缀和还原 O(nm)。总复杂度就是 O(n*m k)。对比一下朴素做法同样是 k 次矩形更新每次最坏遍历整个矩形内部单次 O(nm)总复杂度 O(knm)。假设 nm1000k1000朴素做法是 10^12 次操作差分做法是 210^6 1000 次操作差距达到了百万量级。而且差分方案还有一个天然优势更新和查询是分离的。所有更新阶段只需要记录增量标记不做任何实际数值计算最后统一还原时再用前缀和高效汇总。这种先记账、后结算的思维在很多算法里都能看到只不过差分数组把它用到了极致。4. 实战应用——从图片处理到竞赛题的一鱼多吃4.1 经典应用场景区域批量加值的解题模板二维差分最典型的应用是处理类似给定一个初始全零矩阵执行多次矩形区域加值操作求最终矩阵的问题。这个模板在算法竞赛里几乎是送分题但在工程实践里也有真实对应。举个例子图像处理中我们常需要对局部区域做亮度提升。一张图片可以看作一个二维矩阵每个像素的亮度是一个数值。现在想把画面里几个不同位置的矩形区域都调亮若干个灰度级这时候直接遍历每个像素来做加法在图片尺寸较大、区域又多的时候会非常慢。但如果允许先记录操作、最后统一渲染二维差分就是完美的方案——先记录每个矩形区域的亮度调整量最后一遍前缀和全部应用上去。再比如数据分析里面要在一张销售报表上给多个不同产品区间、多个不同时间段批量添加一个调整系数。这种行方向和列方向同时圈范围的操作也天然适合用二维差分来做。4.2 完整示例给一个 5×6 矩阵做三次矩形更新我带你把一个完整例子从头到尾跑一遍把整个操作流程串起来。假设原始矩阵是一个 5×6 的全零矩阵现在执行三次操作操作1左上角 (2,2) 右下角 (4,5) 加 3 操作2左上角 (1,3) 右下角 (3,4) 加 5 操作3左上角 (3,1) 右下角 (5,2) 加 2先构建 diff初始全部为 0。执行操作1修改四个点diff[2][2] 3 diff[2][6] - 3 # 第5列之后 diff[5][2] - 3 # 第4行之后 diff[5][6] 3执行操作2diff[1][3] 5 diff[1][5] - 5 diff[4][3] - 5 diff[4][5] 5执行操作3diff[3][1] 2 diff[3][3] - 2 diff[6][1] - 2 diff[6][3] 2注意操作3的 x2 已经是第5行x21 是第6行而我们的矩阵只有5行所以 diff 数组必须能容纳第6行——这就是前面强调多开一圈的原因。全部更新完之后做一次前缀和扫描得到0 0 5 5 5 0 0 3 8 8 8 3 0 3 8 8 8 3 2 5 5 5 5 3 2 2 0 0 0 0你可以手动核对一下位置 (2,3) 同时落在操作1和操作2的矩形内所以它是 358位置 (4,2) 只在操作1里所以是 3。矩阵边缘的那些 0 都是边界被正确抵消的结果。能跑出这样的结果说明你对四个标记点的理解已经到家了。4.3 变体与扩展不是只有加值才能用差分二维差分思想不只适用于加法更新。只要你需要对一个矩形区域做同一种批量修改并且可以延迟到最后一并生效都可以考虑差分。常见的变体包括矩形区域赋值比如把某区域整体设为某个值这时候不能直接套用加法差分但可以用区间覆盖的思想配合时间戳或额外的维度信息来处理。矩形区域做异或更新这在某些图形学算法里会出现。异或运算本身满足逆运算所以差分在逻辑上依然成立只是还原的时候前缀和要换成前缀异或。在三维空间里的应用那就是三维差分本质思路完全一样只是偏移点的数量从4个变成了8个复杂度从 O(1) 变成了 O(1) 但点数更多。我个人在实际中用到最多的还是二维加权求和类的离线操作因为大部分批量更新的真实场景都不需要立刻查询某个位置的瞬时值而是等全部改完之后统一出结果。只要符合这个特点二维差分就是最优解。4.4 和二维前缀和的联合使用先更新后查询的终极形态还有一种更高级的玩法就是把二维差分和二维前缀和组合起来先用差分快速完成所有更新再把最终矩阵算出来然后对这个最终矩阵构建二维前缀和数组用来快速回答某个矩形区域内的总和这类查询问题。这时候你就能实现大量更新 大量查询的双重高效。更新阶段是 O(k)还原是 O(n*m)查询阶段每个矩形和是 O(1)。整体性能非常可观。我在实际做报表系统的数据预处理时就用过这个套路——先批量调整多个区域的数据再对不同区域做总和汇总两边都很快。5. 常见问题与排查技巧实录5.1 问题一边界位置数值对不上查了一圈发现是 y21 写成了 y2这是二维差分最经典的坑。很多人理解了四个点的概念但写代码时嫌 1 麻烦或者觉得 y2 就已经是边界了于是写成了 diff[x1][y2] - v。结果就是目标矩形的最后一列被错误地减掉了 v整个矩形右侧少了一块。排查方法很简单找一个小规模矩阵比如 3×3 的矩形更新一个 2×2 的区域手动推一遍结果再让程序打一遍差分数组和还原数组。如果右侧少了一列基本就是边界下标的问题。修起来也简单——边界位置永远要取目标区之外的下一个位置也就是加 1。这个坑踩过一次之后我每次写更新函数之前都会在注释里写清楚右边界减在 y21下边界减在 x21右下加回在 (x21, y21)。5.2 问题二数组越界尤其是 x2 或 y2 刚好是最后一行/列的时候当 x2 等于 n 或 y2 等于 m 时x21 或 y21 就超出了矩阵范围。如果你没有提前把数组开大一圈程序会在更新时直接崩溃。解决方式我在前面已经强调过了——数组统一开成 (n2) × (m2) 大小下标范围从 0 到 n1、0 到 m1这样即使偏移一个位置也不会越界。还有一个小细节不要只在测试数据里没遇到越界就跳过这个处理因为线上数据永远比你想象的更刁钻。开大一圈的成本几乎为零别省这几行数组声明。5.3 问题三前缀和还原时把公式记混了二维前缀和的公式是 f[i][j] f[i-1][j] f[i][j-1] - f[i-1][j-1]。但有些人会和差分构建公式搞混diff[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]。这两个公式的加减号正好相反一个是累加一个是做差。我的记忆方法非常简单构建差分时原始矩阵的值等于当前格子减上方减左方加左上因为这是前缀和的逆运算还原前缀和时当前格子累加的结果等于上方加左方减左上。一个减一个加方向不同但结构对称记住这个对称关系就不容易混了。5.4 问题四差分数组溢出数据范围没算清楚假设原始矩阵元素最大是 10^9操作的次数是 10^5每次加的值也是 10^9那么差分数组里某个位置的值理论上可能累积到 10^14 的级别。如果你用的是 int 类型直接溢出变成负数后面前缀和还原出来的结果就完全错了。这里建议直接用 long long在 Python 里不用操心在 C/Java 里一定要小心。因为 diff 本质上存的是增量标记的累计这些标记本身是中间结果数值可能远大于最终矩阵的任何一个格子。很多人只算了最终结果的大小范围忽略了中间标记的膨胀这是溢出问题的根源。5.5 调试技巧写一个对拍程序验证正确性最后分享一个我很推荐的做法特别适合新手用来验证自己有没有写错。写一个朴素版本的暴力更新函数直接双重循环改矩阵再写一个差分版本然后用随机生成的小矩阵和随机矩形操作反复对拍。如果两个版本跑出来的结果始终一致说明你的差分实现是正确的。这个过程虽然看起来原始但比任何代码 review 都有效。举个例子用 Python 写对拍时随机生成一个 4×5 矩阵、随机生成 20 次矩形更新分别跑朴素版本和差分版本比对最终矩阵是否完全一致。一旦出现不一致就缩小矩阵规模和操作次数打印每一步的差分数组状态定位是哪一次更新出了问题。这个方法在竞赛圈里叫对拍或者暴力对拍是验证算法正确性的黄金标准。我自己在实际调试中踩过的最深刻一次经历就是边界问题。那一次是个人项目里用二维差分处理一块地图的区域权重更新结果右下角的数值怎么都对不上。当时我花了大半个小时排查从更新函数到前缀和还原全部看了一遍最后才发现是 y21 的位置写错了。那次之后养成了一个习惯——每写一个涉及边界的算法第一件事就是在草稿纸上画一个最小的例子把公式和下标全部手动推一遍再写代码。这个习惯帮我避免了很多看起来很蠢但非常耗时的 bug。二维差分数组这个工具说穿了就是用空间换时间、用延迟计算换实时计算的思路和一维差分一脉相承。它不是什么高深莫测的黑科技但用好了确实能解决很多实际问题。你可以先从小矩阵开始练手把构建、更新、还原三步流程走通再逐步应用到具体项目里。在这个过程中如果能把边界处理、溢出防范和调试方法都掌握到位那你就真的把二维差分彻底吃透了。