1. 从“一维”到“二维”差分思想的升维思考在算法和数据结构的领域里差分是一个极其高效且优雅的工具它把区间修改的时间复杂度从 O(n) 降到了 O(1)。很多朋友对一维差分已经驾轻就熟给定一个原数组a我们构造一个差分数组d使得d[i] a[i] - a[i-1]边界特殊处理。这样一来如果我们想对原数组a的区间[l, r]统一加上一个值c只需要在差分数组d上执行d[l] c和d[r1] - c即可。修改完成后对差分数组d求一次前缀和就能得到修改后的a数组。这个“修改O(1)查询O(n)”的套路在处理大量区间更新、单点查询或最终统一查询的场景下比如批量增减、日程安排冲突检测等威力巨大。那么当问题从一条线扩展到一个平面时我们该怎么办想象一下这样的场景你有一个数字图像一个二维矩阵需要对其中任意一个矩形区域内的所有像素值进行统一的亮度调整比如增加某个值或者在一个模拟城市建设的网格地图上你规划了一片矩形区域要新建住宅需要给该区域内所有地块的人口容量增加一个固定值。如果暴力遍历矩形内的每一个格子进行修改假设矩形大小为m*n每次修改就是 O(m*n) 的复杂度。如果这种修改操作非常频繁程序性能很快就会成为瓶颈。二维差分就是一维差分思想在二维空间上的自然延伸。它的核心目标同样没变将对一个子矩阵矩形区域内所有元素的批量修改操作转化为对差分矩阵上仅仅四个顶点的O(1)常数时间修改。理解并掌握二维差分意味着你解锁了处理网格类、图像类、地图类问题中区间区域更新问题的“王牌技能”。很多算法竞赛题目和实际工程问题如图像处理中的ROI操作、游戏中的区域效果、数据统计中的区块累计都会直接或间接用到它。我最初学习时曾试图死记硬背那个“四个点加减”的公式但很快就混淆了。后来我发现必须从一维的原理出发自己推导一遍二维的公式才能真正内化并且在遇到三维甚至更高维差分时也能触类旁通。接下来我们就扔掉死记硬背从最本质的“前缀和”与“差分”的互逆关系出发一步步构建出二维差分的完整操作逻辑。2. 二维前缀和与差分的定义与互逆关系要理解二维差分必须先彻底理解它的“另一半”——二维前缀和。它们是互逆的运算就像加法和减法、积分和微分一样。假设我们有一个原始二维矩阵a其行、列下标均从1开始从1开始能避免很多边界判断的麻烦推荐在算法实现中采用。我们定义二维前缀和矩阵s其中s[i][j]表示原始矩阵a中从左上角(1, 1)到右下角(i, j)所围成的矩形区域内所有元素的和。用公式表示就是s[i][j] a[1][1] a[1][2] ... a[i][j]即所有xi, yj的a[x][y]之和那么如何快速计算s[i][j]呢这里有一个经典的递推公式容斥原理s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]这个公式怎么来的s[i-1][j]是(1,1)到(i-1, j)的和它覆盖了黄色和绿色区域。s[i][j-1]是(1,1)到(i, j-1)的和覆盖了黄色和蓝色区域。这两个加起来黄色区域被加了两次绿色和蓝色区域各加了一次而我们需要的s[i][j]是黄、绿、蓝、红四个区域的总和。多减了一次的黄色区域正好是s[i-1][j-1]最后再加上当前格子a[i][j]红色区域就得到了正确的结果。这个计算过程是 O(1) 的我们可以用双重循环在 O(n*m) 时间内预处理出整个前缀和矩阵s。有了前缀和我们可以在 O(1) 时间内计算任意子矩阵(x1, y1)到(x2, y2)的和sum s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]原理同样是容斥大矩形减去左边和上边的两个矩形再把多减了一次的左上角小矩形加回来。现在主角差分登场了。我们定义二维差分矩阵d它和原始矩阵a满足这样的关系原始矩阵a是差分矩阵d的二维前缀和。换句话说对差分矩阵d求二维前缀和就能得到原始矩阵a。即a[i][j] 从 (1,1) 到 (i,j) 对 d 矩阵求和的结果 用公式表达就是a[i][j] Σ_{x1}^{i} Σ_{y1}^{j} d[x][y]。反过来如何根据原始矩阵a构造它的差分矩阵d呢我们可以利用它们和前缀和s的关系来思考。实际上a可以直接看作它自身的“值矩阵”。构造d的一种直观方法是把每个a[i][j]看作是对一个以(i, j)为左上角(i, j)为右下角的“单点矩阵”进行的修改操作。那么差分矩阵d的初始化可以全为0。然后对于每个位置(i, j)我们执行一次“对以(i,j)为左上角和右下角的1x1矩阵增加a[i][j]”的操作。这个操作作用于差分矩阵d上就是后续要讲的四个点的修改。通过遍历所有(i, j)并执行这个操作最终得到的d矩阵就是a对应的差分矩阵。更常用且简单的初始化方法是利用前缀和递推公式的逆运算。回忆前缀和公式s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]。如果我们把s看作a把a看作d因为a是d的前缀和那么可以得到a[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1] d[i][j]移项后就得到了差分矩阵d的构造公式d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]这个公式可以让我们在 O(n*m) 时间内由原始矩阵a构造出差分矩阵d。注意这个公式是理解后续区域修改操作的关键基础。3. 二维差分矩阵的核心操作区域修改与单点查询现在进入最精彩的部分如何利用差分矩阵d实现对一个矩形区域的快速修改。假设我们要对原矩阵a中以(x1, y1)为左上角(x2, y2)为右下角的矩形区域内的每一个元素都加上一个常数c。在差分的思想下我们不对原矩阵a进行遍历修改而是只修改差分矩阵d上的四个点。操作如下d[x1][y1] cd[x1][y21] - cd[x21][y1] - cd[x21][y21] c为什么修改这四个点就能达到效果我们可以从一维差分类比过来也可以从二维前缀和的定义进行推导。从一维类比理解把二维问题先降维成一维。固定某一行i对列区间[y1, y2]的修改在一维差分里是d[i][y1] c和d[i][y21] - c。现在我们的矩形是从第x1行到第x2行所以我们需要对所有i在[x1, x2]范围内的行都执行这个一维操作。这等价于在d[x1][y1]处c表示从x1行开始所有行的y1列差分都c。在d[x21][y1]处-c表示从x21行开始取消掉刚才对y1列的影响。同理对于y21列这个“终止边界”我们需要在x1行-c在x21行c来抵消。组合起来就是上面四个操作。从二维前缀和公式严格推导推荐掌握记住a是d的二维前缀和。修改后我们希望对于矩形内的点(i, j)即x1ix2, y1jy2其新的a[i][j]等于旧的a[i][j] c对于矩形外的点a[i][j]保持不变。 考虑修改后的差分矩阵d和原差分矩阵d的关系。设变化量delta_d就是我们上面操作的四个点。 那么对于任意点(i, j)修改后的值a[i][j] 对 d 求前缀和 对 (d delta_d) 求前缀和 a[i][j] (对 delta_d 求前缀和)。 现在我们只需要让“对delta_d求前缀和”这个结果在(i, j)位于矩形内时为c在矩形外时为0。观察delta_d的四个操作在(x1, y1)处c这意味着所有以(x1, y1)为矩形右下角或包含该点的前缀和计算都会多一个c。也就是所有ix1, jy1的点其前缀和都会c。在(x1, y21)处-c这会抵消掉对于jy21的列的影响。使得对于ix1, jy21的区域净变化为c (-c) 0。在(x21, y1)处-c这会抵消掉对于ix21的行的影响。使得对于ix21, jy1的区域净变化为c (-c) 0。在(x21, y21)处c由于上面两个-c在(ix21, jy21)的区域多减了一个c因为该区域同时满足两个抵消条件所以需要c补回来使得该区域净变化为0。最终的效果就是只有同时满足ix1, jy1且ix2, jy2的点即我们的目标矩形区域其前缀和变化量才是c。其他区域通过正负抵消变化量均为0。完美达成了目标。注意这里有一个非常关键的细节就是下标的边界。y21和x21可能会超出矩阵的实际范围。在实现时我们通常会把差分数组d的大小声明得比原矩阵a多一行一列例如a是n*md声明为(n2)*(m2)下标从1开始使用。这样x21和y21即使等于n1或m1也仍在数组有效范围内无需特殊判断。这是一个非常重要的编程技巧能极大简化代码逻辑。修改完成后如果我们想得到修改后的原矩阵a只需要对差分矩阵d求一次二维前缀和即可。求前缀和的公式就是前面提到的a[i][j] d[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1]我们可以直接用这个递推公式用d覆盖或计算出新的a矩阵。4. 从理论到实战典型问题分析与代码实现理解了原理我们来看几个典型问题并给出清晰的代码实现模板。我将使用C语言描述但其逻辑可以轻松移植到Java、Python等任何语言。4.1 问题一静态初始化与区域修改这是最基础的场景。我们已知一个原始的n * m矩阵a然后有一系列操作每个操作指定一个矩形区域(x1, y1, x2, y2)和一个值c表示给该矩形区域内所有数加c。所有操作完成后输出最终矩阵。解题步骤根据原始矩阵a构造其差分矩阵d。使用公式d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]。为了方便我们可以假设初始a是全0矩阵然后认为初始矩阵就是通过一系列“对1x1矩阵的添加操作”得到的。更简单的初始化方法是直接创建一个全0的(n2)*(m2)大小的差分数组d然后遍历a对每个(i, j)执行add(i, j, i, j, a[i][j])操作。这个add函数就是上面提到的四步操作函数。对于每一个区域增加操作(x1, y1, x2, y2, c)调用add(x1, y1, x2, y2, c)更新差分数组d。所有操作完成后对差分数组d执行二维前缀和计算得到的结果就是最终矩阵。C代码模板#include iostream #include vector using namespace std; // 二维差分模板 // n, m 为原矩阵大小 // diff 为 (n2) x (m2) 的差分矩阵下标从1开始 void add(vectorvectorint diff, int x1, int y1, int x2, int y2, int c) { diff[x1][y1] c; diff[x1][y21] - c; diff[x21][y1] - c; diff[x21][y21] c; } int main() { int n, m, q; // 矩阵行数列数操作次数 cin n m q; vectorvectorint a(n1, vectorint(m1)); vectorvectorint diff(n2, vectorint(m2, 0)); // 差分数组多开空间 // 1. 读入原始矩阵并构建差分数组 // 方法将每个a[i][j]视为对(i,j)到(i,j)这个单点矩阵的添加操作 for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; add(diff, i, j, i, j, a[i][j]); // 初始化差分 } } // 2. 执行q次区域修改操作 while (q--) { int x1, y1, x2, y2, c; cin x1 y1 x2 y2 c; add(diff, x1, y1, x2, y2, c); } // 3. 对差分数组求前缀和得到最终矩阵 vectorvectorint ans(n1, vectorint(m1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { // 前缀和递推公式 ans[i][j] diff[i][j] ans[i-1][j] ans[i][j-1] - ans[i-1][j-1]; cout ans[i][j] ; } cout endl; } return 0; }4.2 问题二动态初始化与多次查询另一种常见场景是初始矩阵全为0。然后有一系列区域增加操作。操作过程中或操作结束后可能会有查询查询某个位置(i, j)的值或者查询某个子矩阵的和。对于单点查询在每次区域修改后我们只需要对差分矩阵d求前缀和到那个点即可。但如果查询很频繁我们可以在所有修改操作完成后一次性计算出整个前缀和矩阵即最终矩阵然后每次查询就是 O(1) 的。对于子矩阵和查询我们需要的是最终矩阵的二维前缀和矩阵s。流程是所有修改操作作用于差分数组d- 对d求前缀和得到最终矩阵a- 对a求二维前缀和得到s矩阵。之后任何子矩阵和查询都可以用s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]这个公式在 O(1) 时间内回答。这里有一个重要的优化技巧我们可以将“求差分数组d的前缀和得到a”和“求a的前缀和得到s”两个步骤合并。实际上s[i][j]可以直接从d计算出来公式为s[i][j] d[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1]然后s[i][j]再参与下一轮s[i1][j]等的计算。也就是说我们可以把d直接当成“差分的前缀和”的增量来计算最终的前缀和矩阵s。在代码实现上就是用一个数组同时完成累积。4.3 实战中的“踩坑点”与经验总结在实际编码和解题中有几个坑点需要特别注意下标从1开始这是最重要的习惯。将矩阵有效数据存储在索引1~n和1~m并为此多分配数组空间如n2,m2。这能统一处理边界让x21和y21的操作永远在数组范围内避免繁琐的越界检查。我早期因为从0开始下标处理边界条件时bug频出切换到1-base后代码清爽度和正确率大幅提升。差分数组的初始化如果初始矩阵不是全零如何构建初始的差分数组d有两种等价的方法方法A公式法直接套用公式d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]。注意对于i1或j1的边界a[0][*]和a[*][0]视为0。方法B操作法将差分数组d初始化为全零。然后遍历每个(i, j)执行add(i, j, i, j, a[i][j])。这种方法概念上更统一所有变化都通过add操作完成但效率略低O(n*m)次add调用每次是O(1)。在大多数情况下两种方法都可以我个人更偏爱方法B因为逻辑纯粹不易出错。前缀和与差分的互逆性验证在调试时一个很好的方法是先构造一个小的测试用例比如3x3矩阵手动计算其差分矩阵d。然后对d做前缀和看是否能还原出原矩阵a。接着做一个区域修改手动更新d的四个点再求前缀和检查目标区域是否正确增加了c非目标区域是否不变。这个手算过程能极大加深你对公式和边界条件的理解。扩展到“减”操作和更复杂的运算差分不仅限于“加一个常数c”。只要运算满足可逆性和结合律并且区间修改对单点的影响是独立的就可以应用差分思想。例如给一个区间乘以一个常数、进行位运算如异或等。对于“乘一个常数k”其差分操作会有所不同需要重新推导公式。最保险的还是回归本质思考在差分数组上如何操作才能使得前缀和的结果是原数组每个元素乘以k。性能与空间考量二维差分将区域修改的复杂度从 O(矩形面积) 降到了 O(1)。预处理构造差分数组是 O(nm)最终重建矩阵也是 O(nm)。在修改操作远多于查询操作或者修改操作非常密集时优势巨大。空间上需要额外一个(n2)*(m2)的数组通常是可以接受的。在内存极其紧张的情况下可以考虑用一维数组模拟二维或者如果修改和查询是离线的可以使用更复杂的数据结构如二维树状数组或二维线段树但它们单次操作复杂度是 O(log n * log m)代码也复杂得多。二维差分在允许离线处理先收集所有修改最后统一询问的问题中通常是首选的最优解。掌握二维差分后你会发现很多看似复杂的网格更新问题其核心都逃不出这个模型。它是我个人认为必须熟练掌握的基础算法思想之一其重要性不亚于排序和二分查找。通过反复练习将这四个点的修改操作和二维前缀和的递推公式变成肌肉记忆你在处理矩阵类问题时会感到游刃有余。