一、二维差分是什么？
二维差分（2D Difference Array）是一种：
用于“高效进行矩形区域批量修改”的算法技巧。
它通常搭配：
- 二维前缀和（2D Prefix Sum）
- 矩阵区间修改
- 图像区域处理
- 算法竞赛
一起使用。
二、它解决什么问题？
假设有一个二维矩阵：
5 x 5
现在需要频繁进行操作：
给某个矩形区域全部 +v
例如：
(x1,y1) 到 (x2,y2)
全部加上 v。
三、暴力做法的问题
普通写法：
for i in range(x1, x2 + 1):for j in range(y1, y2 + 1):a[i][j] += v
一次修改复杂度：
O(nm)
如果：
- 更新很多次
- 矩阵很大
会非常慢。
四、二维差分核心思想
二维差分本质：
不直接修改整个矩形，
只记录“影响从哪里开始、从哪里结束”。
最后再统一恢复。
五、二维差分更新公式
对于矩形：
[x1,x2] × [y1,y2]
全部加 v：
d[x1][y1] += v
d[x2 + 1][y1] -= v
d[x1][y2 + 1] -= v
d[x2 + 1][y2 + 1] += v
六、为什么这样做？
1. 左上角 +v
d[x1][y1] += v
表示：
从这里开始产生影响。
2. 下边界 -v
d[x2 + 1][y1] -= v
表示：
到 x2 为止，
x2+1 开始取消影响。
3. 右边界 -v
d[x1][y2 + 1] -= v
表示：
到 y2 为止，
y2+1 开始取消影响。
4. 右下角 +v
d[x2 + 1][y2 + 1] += v
这是最容易绕晕的地方。
因为：
下边减了一次
右边减了一次
所以：
右下区域被减了两次
因此需要：
补回来一次
这其实就是：
容斥原理
七、注意：差分数组 ≠ 最终数组
很多人容易误解：
d[i][j]
是不是：
最终矩阵的值
其实不是。
差分数组表示的是：
“变化从哪里开始/结束”
不是最终结果。
八、二维前缀和恢复原矩阵
恢复公式：
a[i][j]
=
d[i][j]
+ a[i-1][j]
+ a[i][j-1]
- a[i-1][j-1]
代码：
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])
恢复后：
d[i][j]
就变成最终矩阵。
九、二维差分为什么是闭区间？
很多人会疑惑：
d[x2+1][y2+1] += v
是不是说明：
右下角也被加了？
其实不是。
真正的有效区域是：
[x1,x2]
[y1,y2]
也就是：
闭区间
因为：
x2+1
y2+1
只是：
“从下一格开始取消影响”
不是最终区域。
十、经典例子
假设：
给矩形:
(1,1) 到 (2,2)
全部 +1
差分更新：
d[1][1] += 1
d[3][1] -= 1
d[1][3] -= 1
d[3][3] += 1
差分数组：
1 0 -10 0 0
-1 0 1
注意：
(3,3)
确实是 +1
但：
这不是最终值。
做二维前缀和后：
1 1 0
1 1 0
0 0 0
真正的 +1 区域：
只有左上 2x2
因此：
d[x2+1][y2+1]+=v
只是：
“抵消重复减法”
不是：
“真的给右下角加值”
十一、复杂度优势
暴力修改
一次：
O(nm)
k次：
O(knm)
二维差分
每次更新：
O(1)
最后统一恢复：
O(nm)
总复杂度：
O(k + nm)
优化巨大。
十二、典型应用场景
二维差分常用于：
1. 图像处理
例如：
- 区域增亮
- 区域模糊
- 像素批量修改
2. 游戏地图
例如：
- AOE范围伤害
- 区域Buff
- 地图染色
3. 算法竞赛
经典题：
- 区间加法
- 矩阵批量更新
- 二维前缀和综合题
十三、一句话总结
二维差分本质：
只记录矩形影响的开始与结束，
最后通过二维前缀和扩散到整个区域。
它不是直接修改矩阵，
而是：