二维差分

这是个非常好的问题！二维差分是解决“区域修改”问题的神器，理解它为什么是这四个点进行 +1, -1 操作是掌握它的关键。

我们将从一维差分开始，逐步推导到二维，并配合图示来直观理解。

一、 预备知识：前缀和与差分的关系

1. 一维前缀和：定义数组 $A$ 的前缀和数组 $S$ 为 $S[i] = A[1] + A[2] + \dots + A[i]$。
   • 性质：区间 $[L, R]$ 的和 = $S[R] - S[L-1]$。
2. 一维差分：定义数组 $A$ 的差分数组 $D$ 为 $D[i] = A[i] - A[i-1]$（其中 $D[1] = A[1]$）。
   • 性质：数组 $A$ 是数组 $D$ 的前缀和，即 $A[i] = \sum_{k=1}^i D[k]$。

一维差分的妙用：区间修改

假设我们要给数组 $A$ 的区间 $[L, R]$ 里的每个数都加上一个值 $v$。

• 朴素做法：遍历 $L$ 到 $R$，执行 $A[i] += v$。时间复杂度 $O(R-L)$，最坏 $O(N)$。
• 差分做法：我们只需要操作两个点！
  1. D[L] += v
  2. D[R+1] -= v

为什么有效？

当我们对修改后的差分数组 $D'$ 求前缀和还原数组 $A'$ 时：

• 对于 $i < L$ 的位置：前缀和 $\sum_{k=1}^i D'[k]$ 没有受到任何影响，数值不变。
• 对于 $L \le i \le R$ 的位置：前缀和累加过程包含了 D[L] += v 这一项，但还没遇到 D[R+1] -= v。所以这些位置的 $A'[i]$ 比原来的 $A[i]$ 多了 $v$。
• 对于 $i > R$ 的位置：前缀和累加过程既包含了 D[L] += v，也包含了 D[R+1] -= v。一加一减抵消了，所以这些位置的数值也不变。

总结：一维差分用两个点的操作，实现了对一段连续区间的修改。

---

二、 推广到二维：从线到面

二维差分的思想是完全一样的：我们构建一个差分矩阵 $D$，使得原矩阵 $A$ 是 $D$ 的二维前缀和。

如果我们想让矩阵 $A$ 中左上角 $(x_1, y_1)$ 到右下角 $(x_2, y_2)$ 的矩形区域内的所有值增加 $v$，我们应该如何操作差分矩阵 $D$？

我们利用二维前缀和的定义：$A[i][j] = \sum_{r=1}^i \sum_{c=1}^j D[r][c]$。

也就是说，$A[i][j]$ 的值等于差分矩阵 $D$ 中左上角 $(1,1)$ 到右下角 $(i,j)$ 的矩形内所有元素的和。

现在，我们来模拟一下操作：

1. 操作一：D[x1][y1] += v

当我们执行这个操作后，对差分矩阵求前缀和来还原矩阵 $A$。

对于任何坐标 $(i, j)$，只要 $i \ge x_1$ 且 $j \ge y_1$，那么在计算前缀和 $\sum_{r=1}^i \sum_{c=1}^j D[r][c]$ 时，都会把 $D[x_1][y_1]$ 这个点包含进去。

效果：以 $(x_1, y_1)$ 为左上角，一直延伸到地图右下角边界的所有区域的值都增加了 $v$。

[Image showing D[x1][y1] += v affects the bottom-right infinite region]

如图所示，绿色区域内的所有点的值都增加了 $v$。但这比我们想要的目标区域（红框）大多了，我们需要把多余的部分减掉。

2. 操作二：D[x2+1][y1] -= v

我们需要把目标区域下方多加的部分剔除。我们选择在 $(x_2+1, y_1)$ 这个点减去 $v$。

当还原矩阵时，对于任何 $i \ge x_2+1$ 且 $j \ge y_1$ 的区域，前缀和计算中会包含 D[x1][y1] 的 $+v$ 和 D[x2+1][y1] 的 $-v$，两者抵消。

效果：抵消了目标区域下方的增长。现在受影响增加 $v$ 的区域变成了以 $(x_1, y_1)$ 为左上角，$(x_2, \text{边界})$ 为右下角的无限长矩形条。

[Image showing D[x2+1][y1] -= v cancels out the region below the target]

如图所示，操作后，深绿色区域是目前净增加 $v$ 的区域，下方的浅绿色区域增量被抵消为 0。

3. 操作三：D[x1][y2+1] -= v

同样的道理，我们需要把目标区域右方多加的部分剔除。我们选择在 $(x_1, y_2+1)$ 这个点减去 $v$。

效果：抵消了目标区域右方的增长。

[Image showing D[x1][y2+1] -= v cancels out the region to the right of the target]

如图所示，操作后，深绿色区域是目前净增加 $v$ 的区域，右侧的浅绿色区域增量被抵消为 0。

4. 操作四：D[x2+1][y2+1] += v（关键的补回）

仔细观察上面的两步抵消操作：

• 操作二减去了目标下方的区域（包含右下角那个重叠区域）。
• 操作三减去了目标右方的区域（也包含右下角那个重叠区域）。

这就导致目标区域右下方的那个区域（即 $i > x_2$ 且 $j > y_2$ 的区域）被减去了两次！一次是 D[x2+1][y1] 带来的影响，一次是 D[x1][y2+1] 带来的影响。而第一次操作 D[x1][y1] 只给它加了一次 $v$。

所以，这个区域现在的值变为：原值 $+ v - v - v =$ 原值 $- v$。这显然不对，我们需要把它补回来。

所以，我们在两者交界的起始点 $(x_2+1, y_2+1)$ 处再加上 $v$。

最终效果：

• 目标区域内（$x_1 \le i \le x_2, y_1 \le j \le y_2$）：只受 D[x1][y1] += v 的影响。净增量 $+v$。
• 目标下方：受 D[x1][y1] ($+v$) 和 D[x2+1][y1] ($-v$) 影响。净增量 $0$。
• 目标右方：受 D[x1][y1] ($+v$) 和 D[x1][y2+1] ($-v$) 影响。净增量 $0$。
• 目标右下方：受全部四个操作影响 ($+v, -v, -v, +v$)。净增量 $0$。

[Image showing final state after D[x2+1][y2+1] += v, only target region is affected]

完美！通过这四步操作，我们精确地只让目标矩形区域内的数值增加了 $v$。

数学公式总结

我们利用了二维前缀和的容斥原理的逆过程。

要让原矩阵 $A$ 的子矩形 $[x_1, x_2] \times [y_1, y_2]$ 增加 $v$。

考察还原后的矩阵 $A'[i][j]$ 的增量 $\Delta A[i][j]$。这个增量是由差分矩阵 $D$ 中位于 $(1,1)$ 到 $(i,j)$ 矩形内的所有修改点的和决定的。

为了只让 $x_1 \le i \le x_2$ 且 $y_1 \le j \le y_2$ 的区域增量为 $v$，其他区域增量为 0，我们构造差分修改：

1. 在 $(x_1, y_1)$ 处 $+v$：启动增量波，覆盖右下方所有区域。
2. 在 $(x_2+1, y_1)$ 处 $-v$：在目标下方截止增量波。
3. 在 $(x_1, y_2+1)$ 处 $-v$：在目标右方截止增量波。
4. 在 $(x_2+1, y_2+1)$ 处 $+v$：修复因两次截止而导致右下方区域被多扣除的错误。

这就是二维差分四个操作点的数学原理，本质上是巧妙运用了前缀和的累加特性和容斥原理来控制影响范围。

非常抱歉！之前的回答中承诺的图示没有正常显示，这确实让抽象的数学原理变得难以理解。

我们将这个问题重新来过。这次我将使用文本字符画来模拟图示，希望能帮你直观地get到二维差分的精髓。

---

核心原理：墨水扩散模型

为了理解二维差分，我们需要建立一个核心的直觉模型：“墨水扩散”。

我们有两个矩阵：

1. $A$ 矩阵（原图）：我们最终想要修改的地图即题目中的 grid。
2. $D$ 矩阵（差分图）：我们的操作台。

它们的关系（关键！）：

矩阵 $A$ 是矩阵 $D$ 的二维前缀和。

这意味着：如果我们改变差分图 $D$ 中的一个点 $D[x][y]$（比如给它 $+v$），当我们还原回 $A$ 图时，这个改变产生的“墨水”会从 $(x, y)$ 开始，向右下方无限扩散，直到地图边界。

图示理解“扩散”：

假设我们在 $D[2][2]$ 的位置滴了一滴墨水（$+v$）。还原成 $A$ 图时，受影响的区域如下所示（用 # 表示受影响增加 $v$ 的区域）：

Plaintext

D图操作：D[2][2] += v

还原后的A图受影响区域：
. . . . .
. # # # #  <- 第2行及下方
. # # # #
. # # # #
. # # # #
  ^
  第2列及右侧

只要坐标 $(i, j)$ 满足 $i \ge 2$ 且 $j \ge 2$，它的值就会增加 $v$。

---

目标：精准打击一个矩形区域

我们的任务：只让红色框选的矩形区域（从 $(x_1, y_1)$ 到 $(x_2, y_2)$）的值增加 $v$，其他地方不变。

我们将使用“包含-排除”法（容斥原理），分四步来达成这个目标。

步骤 1：首次覆盖（范围太大了！）

操作：D[x1][y1] += v

含义：在目标矩形的左上角滴入墨水。

效果图：墨水向右下方扩散，覆盖了目标区域，但也覆盖了目标下方和右方的所有区域。

Plaintext

(假设 x1=2, y1=2, x2=3, y2=3)
目标是中间的 2x2 区域。

操作：D[2][2] += v

A图当前状态（+ 表示增加了 v）：
. . . . .
. + + + +
. + + + +
. + + + +
. + + + +

当前状态：目标区域有了 $+v$，但右边和下面也都有了 $+v$。

步骤 2：切掉下方多余部分

操作：D[x2+1][y1] -= v

含义：在目标矩形底边的下一行，滴入“去色剂”（$-v$）。

效果图：去色剂也向右下方扩散，抵消了步骤1中扩散到下方的墨水。

Plaintext

操作：D[4][2] -= v (因为 x2=3, 所以 x2+1=4)

A图当前状态：
. . . . .
. + + + +  <- 这一行受 D[2][2] 影响 (+v)
. + + + +  <- 这一行受 D[2][2] 影响 (+v)
. . . . .  <- 这一行受 D[2][2](+v) 和 D[4][2](-v) 共同影响，抵消为0
. . . . .  <- 同上

当前状态：目标区域和它右边的区域有 $+v$，下方区域被切掉了。

步骤 3：切掉右侧多余部分

操作：D[x1][y2+1] -= v

含义：在目标矩形右边的下一列，滴入“去色剂”（$-v$）。

效果图：去色剂向右下方扩散，抵消了步骤1中扩散到右侧的墨水。

Plaintext

操作：D[2][4] -= v (因为 y2=3, 所以 y2+1=4)

A图当前状态：
. . . . .
. + + . .  <- 右侧受 D[2][2](+v) 和 D[2][4](-v) 影响，抵消为0
. + + . .  <- 同上
. . . ? ?  <- 注意右下角这个区域！
. . . ? ?

当前状态：目标区域完美了！目标正下方和正右方也被切掉了。但是右下角出了问题。

步骤 4：修复右下角的误伤（关键！）

让我们看看右下角（即 $i > x_2$ 且 $j > y_2$ 的区域，上图中 ? 的位置）发生了什么。

它经历了三次波次：

1. 步骤 1 的墨水扩散：带来 $+v$。
2. 步骤 2 的去色剂扩散：带来 $-v$。
3. 步骤 3 的去色剂扩散：带来 $-v$。

净结果：$+v - v - v = -v$。

右下角区域的值不仅没保持不变，反而变小了！这是因为我们切下方和切右方时，右下角这块公共区域被切了两次。

操作：D[x2+1][y2+1] += v

含义：在右下角的交界处，补加一滴墨水，把多扣的补回来。

Plaintext

操作：D[4][4] += v

A图最终状态：
. . . . .
. + + . .
. + + . .
. . . . .  <- 右下角受 +v, -v, -v, +v 四个操作影响，最终抵消为0
. . . . .

总结

这四个点的操作本质上就是一次完美的“填补与切割”游戏：

1. D[x1][y1]++：先铺满一大片，保证目标区域被覆盖。
2. D[x2+1][y1]--：把目标下面的多余区域切掉。
3. D[x1][y2+1]--：把目标右面的多余区域切掉。
4. D[x2+1][y2+1]++：因为第2步和第3步都切掉了右下角，导致右下角被多切了一次，所以要补回来。