C++ 基础算法 - 二维差分

2023-07-21 23:39 作者:DecemberFox 0人读过 | 我要投稿

今天学习二维差分。

一维差分

在学习二维差分之前，先要学会一维差分

这里加强对一维差分的理解

将一位差分的操作变为前缀的变化，如下列数列 ( 从 0 开始编号 )

将 2 至 5 的数字 ( 对应数列中 7，8，2，1 ) 增加 $k$ ，且 $k%3D4$ ，那么差分数组从全为 0 变为

此时差分数组的前缀和将分为三段 ( 相较于原来全为 0 的差分数组 )

第一段为 0 至 1 ( 对应数列中 9，4 ) 的前缀和不变，仍然为 0
第二段为 2 至 5 ( 对应数列中 7，8，2，1 ) 的前缀和增加了 4
第三段为 6 至 7 ( 对应数列中 0，3 ) 的前缀和不变，4 与 -4 相互抵消

正好对应了将 2 至 5 的数字增加 4 的概念

因此我们可以知道，差分数组中每一位的前缀和表示的就是原数列该位置的增值

即 $a_i(%E4%BF%AE%E6%94%B9%E5%90%8E)%3Da_i(%E4%BF%AE%E6%94%B9%E5%89%8D)%2Bsumdiff_%7Bi%7D$ ， $sumdiff_i$ 表示的是差分数组 $diff$ 的前缀和，转化后可得 $sumdiff_i%3Da_i(%E4%BF%AE)-a_i(%E5%8E%9F)$ ，修指修改后的，原指原来的

所以每一位的增值 $p_i%3Da_i(%E4%BF%AE)-a_i(%E5%8E%9F)%3Dsumdiff_i$ ，这就使用数学的方法解释了差分数组的作用，最后我们得到了这样的式子

$p_i%3Dsumdiff_i%3Da_i(%E4%BF%AE)-a_i(%E5%8E%9F)$

这样看起来差分的复杂度只有一次修改的复杂度 $O(1)$ ,修改 $k$ 次，复杂度也仅有 $O(k)$ 次，看起来时间复杂度十分好，但是如果算上查询 $m$ 次，复杂度变为 $O(k%2Bmn)$ ，并不高效

因此差分仅适合在数据范围较小的题目使用，遇到数据范围更加大的题目时就需要使用复杂度为 $O(klog_2n%2Bmlog_2n)$ 的树状数组和线段树来实现了，但因为差分编码简单，在适合的时候往往选择容易编写的差分

二维差分

由一维差分可以知道，二维差分就是选择一个矩形区域，将区域内的所有元素增加或减少一个数 $t$

简单做法 ( 并不正确 )

本段通过思考简单的做法推动二维差分实现，因此本段不是正解，可以选择性阅读本段

修改

先考虑将矩形区域处理一下，变为一条条数列的区间从而使用普通一位差分修改

如上图，将 $A(x_a%2Cy_a)$ 至 $D(x_d%2Cy_d)$ 的值加上 $t$ ，再将 $C(x_c%2Cy_c)$ 至 $B(x_b%2Cy_b)$ 修改为 $-t$ ，复杂度为 $O(height_%7B%E4%BF%AE%E6%94%B9%7D)$

查询

在查询时，如果询问的矩形区域 ( $%E7%9F%A9%E5%BD%A2_%7BA'B'C'D'%7D$ ) 正好没有与修改矩形区域 ( $%E7%9F%A9%E5%BD%A2_%7BACBD%7D$ )，的左边线 ( $AD$ ) 相交，这时在统计时就无法加上修改矩形区域修改的值，因此，我们不能从询问的矩形区域的左边线 ( $A'C'$ )，开始计算，应该从其对应在 $y$ 轴上的点 $A''$ 与 $C''$ 开始计算

这种方式将每一行都看做一个差分数组，都做了一次差分，时间复杂度为 $O(height_%7B%E6%9F%A5%E8%AF%A2%7Dx_%7B%E6%9F%A5%E8%AF%A2%7D)$

不难发现，这种方法的时间复杂度比较劣，还有提升的空间

正确做法

本段讲解的才是正确的二维差分

修改

我们尝试将修改操作的复杂度降至 $O(1)$ ，我们知道一维差分可以将所有 $a_i$ ( $l%5Cle%20i$ ) 的数值增加 $t$ ，通过两次修改实现区间修改

将这个思想推广至二维，那么二维差分就应该可以将所有 $a_%7Bi%2Cj%7D$ ( $x_l%5Cle%20i%2Cy_l%5Cle%20j$ ) 的数值增加 $t$

例如上面三连展示的图片，我们将右下角看做原点， $%E7%9F%A9%E5%BD%A2_%7BBCAD%7D$ 是要修改的矩形区域，这时候我们将上一段所述的 $x_l%3Dx_B%2Cy_l%3Dy_B$ ，那么点 B 左上的所有点都增加了 $t$ ，但是我们更改的目标是 $%E7%9F%A9%E5%BD%A2_%7BBCAD%7D$ ，如果使用上述方法将会更改整一个 $%E7%9F%A9%E5%BD%A2_%7BOFBH%7D$ ，而如果要消除影响，就可以将 $%E5%A4%9A%E8%BE%B9%E5%BD%A2_%7BOFCADH%7D$ 再次减去 $t$

看看这个多边形的样子，是不是很熟悉

所以，我们以右上角为原点并加入二维前缀和的思想，并利用公式

$sum_%7Bx_b%2Cy_b%7D%3Dsum_%7Bx_b%2Cy_a-1%7D%2Bsum_%7Bx_a-1%2Cy_b%7D-sum_%7Bx_a-1%2Cy_a-1%7D$

上述公式在二维前缀和中讲过了

这时候我们需要反过来使用，因为我们先创造了 $sum_%7Bx_b%2Cy_b%7D$ 的影响 ( 增加 $t$ )，所以我们在后面将消除其影响，就可以使用这个式子， $sum_%7Bx_b%2Cy_a-1%7D%2Bsum_%7Bx_a-1%2Cy_b%7D-sum_%7Bx_a-1%2Cy_a-1%7D$

这三个项就是消除的关键，因为增加了 $t$ ，所以 $sum_%7Bx_b%2Cy_b%7D$ 的值也就为 $t$ ，因此 $sum_%7Bx_b%2Cy_a%7D$ 与 $sum_%7Bx_a%2Cy_b%7D$ 都要等于 $-t$ 以消除影响，但是我们发现 $sum_%7Bx_a-1%2Cy_a-1%7D$ 被两次操作都减了一次 $t$ ，因此需要在 $sum_%7Bx_a-1%2Cy_a-1%7D$ 再加上一次 $t$ ，这其实就是前缀和的思路