二维差分数组详解：从原理推导到代码实现与实战应用

1. 从一维到二维先弄清差分数组到底在解决什么问题二维差分数组听名字好像是差分数组的“升级版”很多朋友一上来就去死磕二维的公式结果看到四个点的加减操作就懵了。我的建议是先别急着看二维先把一维差分的本质吃透因为二维的所有逻辑都是一维的推广一维想明白了二维就是顺水推舟的事。先复习一下一维差分。假设你有一个长度为 n 的数组 a现在要执行 m 次区间加操作每次把 [l, r] 范围内的所有元素都加上一个值 v。最暴力的做法是每次遍历区间时间复杂度 O(n)m 次就是 O(n*m)。差分数组的做法是构造一个差分数组 d满足 d[i] a[i] - a[i-1]规定 d[0] a[0]那么对原数组 a 在 [l, r] 区间加 v等价于执行 d[l] v 和 d[r1] - v 两个操作。所有操作做完后再对 d 做一遍前缀和就能还原出最终的 a。这里值得停下来想一想为什么区间加能被拆成端点操作因为差分数组记录的是相邻元素之间的“变化量”。区间内部所有元素统一加 v那么区间内部的相邻差值是不变的变化的只有两个端点——左端点 l 与其前一个元素的差值增加了 v右端点 r 与其后一个元素的差值减少了 v。所以只需要修改两个点就能代表一整段区间的变化这就是差分的核心思想用端点变化代替范围变化。二维差分就是把这个思想平移到二维平面上。它解决的核心问题是给定一个二维矩阵比如 n 行 m 列的网格执行 q 次子矩阵加操作每次把左上角为 (x1, y1)、右下角为 (x2, y2) 的矩形区域内所有元素加上 v最后输出整个矩阵的最终值。暴力做的话每次操作要遍历矩形内的所有格子复杂度 O(nm)q 次就是 O(qnm)数据稍大就直接爆炸。二维差分可以把每次子矩阵更新的代价降为 O(1)只改四个点最后做一次二维前缀和还原总复杂度 O(nm q)。学习二维差分之前你还需要先把二维前缀和搞明白。二维前缀和计算的是“从 (1,1) 到 (i,j) 这个矩形区域内所有元素的和”用容斥原理递推s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]。差分和前缀和本来就是互逆操作一维里“差分数组求前缀和还原原数组”二维里“差分矩阵求二维前缀和还原原矩阵”。所以先确认自己二维前缀和的公式烂熟于心否则后面看差分矩阵的公式会觉得像天书。2. 二维差分矩阵的构造原理与公式推导很多人第一次接触二维差分看到网上教程直接给结论对左上角 (x1, y1)、右下角 (x2, y2) 的子矩阵加 v只需要修改四个点diff[x1][y1] v diff[x1][y21] - v diff[x21][y1] - v diff[x21][y21] v然后就开始背公式背完就忘忘了再看一遍下次遇到还是不会。问题出在没理解这四个点为什么这么改。我们从二维前缀和还原的角度来逆推。假设我们有一个差分矩阵 diff对 diff 做二维前缀和之后得到原矩阵 a也就是说a[i][j] sum of diff[1..i][1..j]这个式子的含义是原矩阵中位置 (i, j) 的值等于差分矩阵中所有满足“行 i 且列 j”的位置的值之和。注意这句话的几何意义位置 (i, j) 会把差分矩阵左上角到它自身这个矩形内所有的 diff 值都“收集”起来。现在我们要实现的效果是让以 (x1, y1) 为左上角、(x2, y2) 为右下角的矩形内所有 a 值都加上 v矩形外部的 a 值不变。怎么做到我们来看第一个操作 diff[x1][y1] v。所有满足行 x1 且列 y1 的位置在做二维前缀和时都会把这个 diff 值收集进去。这就意味着如果只做这一步那么从 (x1, y1) 到矩阵右下角的整个大区域所有值都会加上 v。这显然是“加多了”因为目标矩形只到 (x2, y2) 为止。接下来就需要“削掉”多出来的部分。多出来的区域有两块一块是行在 [x1, x2] 但列在 [y21, m] 的范围即目标矩形的正右方一块是列在 [y1, y2] 但行在 [x21, n] 的范围即目标矩形的正下方。另外还有一个区域是行和列都超出的部分即右下方的矩形它被上面两块重复削了一次。所以第二和第三个操作分别是 diff[x1][y21] - v 和 diff[x21][y1] - v。第一个减去的是右方区域第二个减去的是下方区域。但这样右下方的矩形被减了两次多减了一次所以第四个操作 diff[x21][y21] v 把多减的那一次加回来。四个操作合起来就精确地实现了目标矩形内部加 v、外部不变的效果。这个逻辑和二维前缀和公式中的容斥原理如出一辙本质就是“加整块、减两块、加回一块”。理解了这一点之后直角坐标系画网格图看一看会更直观。你把矩阵想象成一张格子纸diff[x1][y1] v 是在左上角“投放”一个正值它会像水波一样向右下方扩散三个后续操作就是在对应边界处“投放”负值来拦截扩散。每次子矩阵更新实际是在差分矩阵上维护这个“扩散—拦截”的痕迹最终前缀和还原时痕迹叠加就形成了目标效果。再看构造差分矩阵本身。如果给你一个初始矩阵 a让你求出它的差分矩阵 diff有两种等价方式。第一种是直接照定义推先对所有位置假设 diff 全为 0然后遍历矩阵的每个元素把 a[i][j] 看作一次“单点矩形加”操作——即对左上角 (i, j)、右下角 (i, j) 的 1x1 子矩阵加 a[i][j]调用四个点的更新逻辑即可。第二种是恢复公式diff[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]本质上是二维前缀和的逆运算。实战中我更推荐第一种思路因为它和后面的子矩阵更新操作统一起来了写代码不容易出错。第二种方式适合笔试手推场景但新手容易把符号记乱。这里给你一个建议把二维差分矩阵的更新函数和构造过程统一成同一个函数后续所有逻辑都复用这一个函数bug 率会大幅下降。3. 核心代码实现差分标记与二维前缀和还原理论讲透了上代码。我用 C 写一个完整可运行的模板因为竞赛和面试里 C 用得最多但思路完全同步到 Python、Java、Go 都没问题。假设矩阵行数为 n、列数为 m下标从 1 开始这样差分矩阵的边界处理会清爽很多。先看子矩阵更新函数// 对左上角(x1,y1)、右下角(x2,y2)的矩形区域加上 val void add(int x1, int y1, int x2, int y2, int val) { diff[x1][y1] val; diff[x1][y2 1] - val; diff[x2 1][y1] - val; diff[x2 1][y2 1] val; }这个函数就四行非常短但它是整个二维差分的主心骨。需要特别注意的是下标边界问题。所有 diff 数组要开得比原矩阵大我习惯开 (n 2) * (m 2)这样当 x21 或 y21 恰好等于 n1 或 m1 时不会发生数组越界。严格来说这些越界位置的修改是无意义的因为前缀和还原时不会用到它们但为了代码简洁和避免分支判断多开一圈是最省心的做法。接下来是构造差分矩阵的两种方式先看推荐的方式——从原矩阵 a 通过单点更新构造// 初始化 for (int i 1; i n; i) { for (int j 1; j m; j) { add(i, j, i, j, a[i][j]); } }这段代码的含义是把每个原始元素 a[i][j] 看成一次对 1x1 子矩阵的加操作。初始化完成之后diff 矩阵就是 a 的差分矩阵。这种方式逻辑统一、不易出错缺点是常数略大但大多数题目完全够用。再看直接公式构造方式for (int i 1; i n; i) { for (int j 1; j m; j) { diff[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]; } }这段代码更短但如果你对容斥公式不熟建议不要在生产代码里直接用它。我见过很多人在手写时把符号写错排查半天发现是初始化错了。相比之下第一种方式虽然啰嗦一点但可读性好、和更新操作完全一致更重要的是不容易出错。所有更新操作都执行完毕之后需要对 diff 做二维前缀和还原出原矩阵for (int i 1; i n; i) { for (int j 1; j m; j) { a[i][j] diff[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1]; } }这里的 a 数组在做前缀和过程中被逐步覆盖成最终答案。注意递推顺序i 从小到大、j 从小到大因为 a[i-1][j] 和 a[i][j-1] 必须已经是还原好的值。这个顺序不能乱否则结果全错。如果你不想覆盖原始数据可以新建一个 res 数组但覆盖写通常更省内存。为了让你看完整的执行流我贴一个完整示例#include bits/stdc.h using namespace std; const int N 1005; int a[N][N], diff[N][N]; void add(int x1, int y1, int x2, int y2, int val) { diff[x1][y1] val; diff[x1][y2 1] - val; diff[x2 1][y1] - val; diff[x2 1][y2 1] val; } int main() { int n, m, q; cin n m q; for (int i 1; i n; i) for (int j 1; j m; j) cin a[i][j]; // 构造差分矩阵 for (int i 1; i n; i) for (int j 1; j m; j) add(i, j, i, j, a[i][j]); // 执行 q 次子矩阵加操作 while (q--) { int x1, y1, x2, y2, v; cin x1 y1 x2 y2 v; add(x1, y1, x2, y2, v); } // 二维前缀和还原最终矩阵 for (int i 1; i n; i) for (int j 1; j m; j) a[i][j] diff[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1]; for (int i 1; i n; i) { for (int j 1; j m; j) cout a[i][j] ; cout \n; } return 0; }代码很简单核心就是 add 函数和最后的双重循环。实际做题时你会碰到一些变种比如不给出初始矩阵、全部从 0 开始那就跳过构造步骤直接执行 q 次 add最后前缀和还原即可。Python 版本的思路一模一样只是循环写法更简洁def add(x1, y1, x2, y2, val): diff[x1][y1] val diff[x1][y2 1] - val diff[x2 1][y1] - val diff[x2 1][y2 1] val这里要多提醒一句Python 的二维数组初始化一定要用列表推导式不要用[[0] * (m2)] * (n2)这种写法否则每一行都是同一个对象的引用改一个等于改全部新手经常踩这个坑。4. 边界条件、复杂度分析与常见错误排查二维差分看起来简单但实际写题时错误率不低。我把自己踩过的坑和帮别人 debug 时高频出现的问题整理成一张速查表你一定用得上。问题现象可能原因排查思路结果整体偏大/偏小diff 数组越界或被多轮复用检查 add 中的 x21、y21 是否越界diff 数组是否清零只有部分区域正确下标从 0 开始导致边界错位确认 x11、y11避免 0 下标参与运算值呈“阶梯状”错乱前缀和还原顺序错误确认双层循环都是从小到大不能先处理完列再处理行多次测试数据相互污染diff 数组未重复初始化每次新用例前用 memset 或 fill 清零Python 修改一个值影响整行二维列表初始化用了乘法改用[[0] * (m2) for _ in range(n2)]这里边最值得展开的是下标从 0 开始的问题。不少教材和模板默认从 1 开始就是因为边界处理干净。如果你非要从 0 开始那么 add 函数里的“加 1”操作全都要仔细重新推导比如 diff[x1][y1] v 保留但 diff[x1][y21] - v 这里的 y21 在边界时容易变成越界索引。与其反复推不如直接统一从 1 开始读入、从 1 开始处理、从 1 开始输出省下的时间够多刷两道题。再谈空间优化。标准的二维差分需要 (n2)*(m2) 的 diff 数组。如果题目内存限制极紧可以在原地完成——利用原矩阵 a 来存 diff等所有 add 操作做完后再原地跑前缀和。但原地操作非常容易覆盖还没用到的原值我建议只有当你对差分的原理和还原顺序都烂熟于心时再这么干日常写题老老实实开新数组即可空间换时间、换稳妥值。复杂度方面初始化构造 O(nm)每次子矩阵更新 O(1)最终前缀和还原 O(nm)总时间复杂度 O(nm q)空间复杂度 O(nm)。这个复杂度是二维差分最大的卖点。对照来看暴力更新是 O(qnm)当 nm1000、q100000 时暴力是 10^11 量级的操作跑完要几个小时差分只需要 10^6 10^5 量级毫秒级出结果。这就是为什么二维差分在处理大规模矩阵更新的场景里几乎不可替代。使用二维差分时还有一个前提条件必须注意所有更新操作完成之后才能进行前缀和还原并查询答案。也就是说它适合“先批量更新、再统一查询”的任务模式。如果你需要在更新过程中随时查询某个位置的值那差分就力不从心了需要配合树状数组或线段树等支持动态查询的数据结构。判断一道题能不能用二维差分就看它是否满足“离线更新、最后统一求结果”这个特征。5. 实战应用场景与典型题目拆解二维差分在真实问题里有多能打我给你拆几个典型的应用场景每个都是可以直接套模板的。第一个场景是矩阵区域批量增量。比如你在做一个游戏地图n*m 的网格代表地形每次地震事件会把某个矩形区域的海拔统一抬升 v执行 q 次后输出最终地形。这就是最朴素的二维差分应用直接套模板即可没有任何额外难度。第二个场景是二维离散化与扫描线结合。有些题目给你的是坐标点而不是规整的矩阵。比如在一个大坐标平面上有若干个矩形每个矩形有不同权重求最终某个点的总权重。由于坐标范围可能高达 1e9不能直接开二维数组需要把涉及的 x、y 坐标分别离散化映射到小网格中再用二维差分处理。这类题目把“离散化 二维差分”组合起来用是二维差分离谱应用里最常见的一个方向。第三个场景是矩阵中的连通区域标记。假设你想在矩阵中找到所有满足某条件的连通区域可以先对满足条件的位置统一加 1再通过前缀和快速判断某个区域的覆盖情况。当然这种场景不如前两种直接但很多题解的“套路化”思路里确实能看到二维差分的影子。还有一类是模拟题中的碰撞与覆盖统计。比如在一张网格图上有若干个形状矩形、L 形等的物体每个物体覆盖的格子需要累加一次计数最后输出覆盖次数超过 k 的格子数量。如果物体都是矩形直接二维差分如果是不规则形状可以先拆成多个矩形再分别 add。经典题目方面你可以去刷 LeetCode 上的 598“区间加法 II”虽然是简化版以及各大 OJ 上的“差分矩阵”“子矩阵累加和”类题目。竞赛圈里二维差分经常作为套题的“基础工具”出现——它本身不考验思维难度但一旦你现场临时推导很容易出错所以平时把模板练熟赛时直接默写能省下大量时间。如果遇到升级版——三维差分思路是一样的。三维空间的立方体区域加 v需要修改 8 个点对应容斥展开的符号是“一加、三减、三加、一减”也就是二项式系数的符号规律。理解了二维的四个点是怎么来的三维的八个点你也能推出来。掌握了这个规律以后遇到任意维度区间加问题都能举一反三。6. 从会写到不写错我总结的实操心得二维差分这部分内容我前后给不少人讲过也帮人排过不少雷。最后分享几个我自己的实操心得。第一写之前先在草稿纸上画 4x4 或 5x5 的小网格手推一遍。不需要多复杂就随便挑一个子矩阵比如 (2,2) 到 (3,4)把四个点的 add 操作标记出来沿着前缀和还原顺序走一遍亲眼看到矩形内部加上了值、外部没变你对公式的记忆就彻底活了。之后刷题遇到各种变形心里都有一个“画面”兜底。第二把 add 函数和还原循环当成肌肉记忆来练。二维差分的代码本身没有任何难度难的是你在紧张的环境下还能不出边界错误。我的建议是不要每次都现场推公式而是把这个模板写到自己的代码库里确保能在 30 秒内默写出来。多练自然就熟了。第三善用中间打印调试。如果你发现结果不对第一步别猜直接在还原之前把 diff 矩阵打出来看。如果 diff 的四个标记点位置符合预期说明 add 没问题问题出在还原循环如果 diff 本身就不对重点检查 add 的边界和操作次数。这种二分定位法能帮你快速锁定问题。第四留意题目给的是“操作次数”还是“最终值状态”。有些题不给你初始矩阵只给你 q 次操作让你输出最终结果有些题给初始矩阵又给了操作。这两种情况只是构造步骤的取舍别搞混。拿到题先确认输入模型再决定代码结构。二维差分是一个典型的“会者不难、难者不会”的工具型知识点。它的推导门槛不高但实用性极强。我希望这篇讲完你不仅会默写四个 add 公式还能在面试里把“为什么是这四个点”讲得头头是道——因为面试官问到底层原理时支支吾吾背公式是最减分的表现。把原理吃进脑子然后去练两道题它就会成为你工具箱里一个再也不会丢的部件。