1. 为什么需要二维差分数组——从一维到二维的思维变化
1.1 先复习一维差分，别着急直接跳过来
咱们先把一维差分彻底搞明白，因为二维差分是一维差分的自然延伸，一维没吃透，二维就是个空中楼阁。
假设你有一个长度为 n 的数组，现在要执行 m 次操作，每次都是把某个区间 [l, r] 内的所有元素同时加一个值 v。如果朴素地写，每次都遍历 l 到 r，操作复杂度是 O(n)，m 次就是 O(nm)，数据量一上来直接超时。这时候差分数组就上场了：你先维护一个 diff 数组，每次操作只改两个位置——diff[l] += v，diff[r+1] -= v，然后全部操作结束之后，对 diff 做一次前缀和，就能还原出最终数组。整个过程的复杂度从 O(nm) 降到了 O(n+m)。
一维差分为什么能用？关键在于"区间加"这种操作，它本质上是给一段连续区域打上统一的增量标记，而前缀和可以把这个标记还原回每个位置原有的数值。差分数组天生就是为"区间多次更新 + 最后统一查询"这种场景准备的。
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 = 1，diff[2][1] = 4 - 1 = 3，diff[2][2] = 5 - 2 - 4 + 1 = 0。算完整个 diff 矩阵之后，你对它做一次二维前缀和扫描，就能还原出原矩阵。这就是差分数组"用前缀和还原"的核心闭环。
2.2 矩形更新的四个坐标点：面积法一次看懂
现在进入最关键的部分——如何用 O(1) 的时间完成一个矩形区域的加值操作。
假设现在要把左上角 (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光背下来不行，我们来理解它为什么是这四个位置。你可以把 diff 的每一次更新看作是对最终前缀和结果做的一个"面积修正"。我们的目标是：在 (x1, y1) 到 (x2, y2) 这个矩形内部，每个位置在还原时都能多出 v；矩形之外不能受影响。
- 在 (x1, y1) 处加 v，相当于从左上角开始，把整个右下方向的区域都加上了 v，影响范围是一个无限延伸的右下三角形区域。
- 但这块区域太大了，超出了目标矩形的宽度，所以要在 (x1, y2+1) 处减 v，把目标矩形右侧之外的部分"砍掉"。
- 同理，也要把目标矩形下侧之外的部分砍掉，所以在 (x2+1, y1) 处减 v。
- 但是右侧和下侧的减少区域在 (x2+1, y2+1) 处重叠了，重叠的部分被减了两次，所以要在那里加 v 补偿回来。
你把这个过程在纸上画一下，会发现四个点形成的"加减模式"正好把最终的影响范围限制在了目标矩形内。理解了这层面积逻辑，再结合前缀和公式，这四个点的来源就非常清晰了。
2.3 为什么是 y2+1 而不是 y2？边界地带的严谨推导
很多初学者最容易问的一个问题是：修改边界为什么不用 (x1, y2) 而用 (x1, y2+1)？这其实涉及到前缀和的精确语义：前缀和扫描到位置 (i, j) 时，diff[i][j] 的累加会影响到包括 (i, j) 在内的所有右下方位置。如果我们要让第 y2 列还保留加值，而第 y2+1 列之后不受影响，那么"减 v"这个操作必须发生在 y2+1 列开头，也就是下标 y2+1 的位置。放在 y2 位置的话，连第 y2 列自己也被减掉了，等于这个矩形右侧边界少了一列。
同样的道理适用于 x2+1 行。这个细节在实战里特别容易出错——很多人写代码时随手就把 y2+1 写成了 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 的尺寸我开了 m+2 行、n+2 列，多出来的一圈是留给边界用的。比如当 x2 等于最后一行时，x2+1 会落到 n+1，如果没有额外多开一列，程序就会越界。多开一圈是写这类题和代码时最省心的习惯，别扣那点空间。
构建差分矩阵的本质，就是对原始矩阵做一次"离散二阶差分"。你可以理解成把每个格子的值转换成了一个"增量标记"，这些标记只有在做前缀和时才会被还原出来。构建过程的时间复杂度是 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)。假设 n=m=1000，k=1000，朴素做法是 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执行操作2：
diff[1][3] += 5 diff[1][5] -= 5 diff[4][3] -= 5 diff[4][5] += 5执行操作3：
diff[3][1] += 2 diff[3][3] -= 2 diff[6][1] -= 2 diff[6][3] += 2注意操作3的 x2 已经是第5行，x2+1 是第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的矩形内，所以它是 3+5=8；位置 (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 问题一：边界位置数值对不上，查了一圈发现是 y2+1 写成了 y2
这是二维差分最经典的坑。很多人理解了四个点的概念，但写代码时嫌 +1 麻烦，或者觉得 y2 就已经是边界了，于是写成了 diff[x1][y2] -= v。结果就是目标矩形的最后一列被错误地减掉了 v，整个矩形右侧少了一块。
排查方法很简单：找一个小规模矩阵，比如 3×3 的矩形，更新一个 2×2 的区域，手动推一遍结果，再让程序打一遍差分数组和还原数组。如果右侧少了一列，基本就是边界下标的问题。修起来也简单——边界位置永远要取"目标区之外的下一个位置"，也就是加 1。这个坑踩过一次之后，我每次写更新函数之前都会在注释里写清楚：右边界减在 y2+1，下边界减在 x2+1，右下加回在 (x2+1, y2+1)。
5.2 问题二：数组越界，尤其是 x2 或 y2 刚好是最后一行/列的时候
当 x2 等于 n 或 y2 等于 m 时，x2+1 或 y2+1 就超出了矩阵范围。如果你没有提前把数组开大一圈，程序会在更新时直接崩溃。解决方式我在前面已经强调过了——数组统一开成 (n+2) × (m+2) 大小，下标范围从 0 到 n+1、0 到 m+1，这样即使偏移一个位置也不会越界。
还有一个小细节：不要只在测试数据里没遇到越界就跳过这个处理，因为线上数据永远比你想象的更刁钻。开大一圈的成本几乎为零，别省这几行数组声明。
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 次矩形更新，分别跑朴素版本和差分版本，比对最终矩阵是否完全一致。一旦出现不一致，就缩小矩阵规模和操作次数，打印每一步的差分数组状态，定位是哪一次更新出了问题。这个方法在竞赛圈里叫"对拍"或者"暴力对拍"，是验证算法正确性的黄金标准。
我自己在实际调试中踩过的最深刻一次经历，就是边界问题。那一次是个人项目里用二维差分处理一块地图的区域权重更新，结果右下角的数值怎么都对不上。当时我花了大半个小时排查，从更新函数到前缀和还原全部看了一遍，最后才发现是 y2+1 的位置写错了。那次之后养成了一个习惯——每写一个涉及边界的算法，第一件事就是在草稿纸上画一个最小的例子，把公式和下标全部手动推一遍，再写代码。这个习惯帮我避免了很多看起来很蠢但非常耗时的 bug。
二维差分数组这个工具，说穿了就是"用空间换时间、用延迟计算换实时计算"的思路，和一维差分一脉相承。它不是什么高深莫测的黑科技，但用好了确实能解决很多实际问题。你可以先从小矩阵开始练手，把构建、更新、还原三步流程走通，再逐步应用到具体项目里。在这个过程中，如果能把边界处理、溢出防范和调试方法都掌握到位，那你就真的把二维差分彻底吃透了。
