差分是前缀和的逆运算

对于数组 $a_1, a_2, a_3, \ldots, a_n$ 和数组$b_1, b_2, b_3, \ldots, b_n$ 如果 $a_i = b_1+b_2+b_3+..+b_i$, 那么我们称 a 数组是 b 数组的前缀和, b 数组是 a 数组的差分. 对于任意 bi 有 $b_i = a_i - a_{i-1}$

由上可得$a_i$与 $b_i$的关系, 那么反过来 $b_i = f(a_i) ?$

$$ \begin{aligned} b_1 &= a_1 \newline b_2 &= a_2 - a_1 \newline b_3 &= a_3 - a_2 \newline & \ \vdots \newline b_n &= a_n - a_{n-1} \end{aligned} $$

差分有什么用?

假设我们已经有b 数组了, 那么我们如果想要求a数组, 只要求一遍前缀和就可以了.

那么我们就可以以 O(N)的时间从 b 数组得到 a 数组

回忆下前缀和的作用是什么呢? — 快速求区间和

对于给定的区间 [l, r] , 让 a 在这个区间的数全部加上常数c , 如果暴力遍历这些数那么就是 O(N)的

但是如果用差分来做的话就可以做到 O(1)

为什么呢?

考虑当我们对 a 数组做了加常数 c 的操作, b 数组发生了什么变化? 或者说 b 数组的什么操作能使得 a 数组在指定区间内的数都加上 c

其实就是对 $b_l $ 加上常数 c 之后再求前缀和即可得到 $a_l + c$ .

当我们对$b_l+c$之后, 会导致原数组的 [$a_l, a_{l+1}, a_{l+2},…, a_r, a_{r+1}, a_{r+2},…,a_n$]这些数全部加上 c, 也就会变成 [$a_l+c, a_{l+1}+c, a_{l+2}+c,…, a_r+c, a_{r+1}+c, a_{r+2}+c,…,a_n+c$]

但是我们只需要让 [$l,r$]之间的数加上常数 c, (r+1)之后的数不能加上 c, 所以我们就得打一个补丁来进行修正, 也就是让 $b_{r+1} - c $ , 这样(r+1)之后的原数组的数就不会加上 c 了. 如下图所示

原本我们想要让前缀和数组的数在 [$l,r$]之间的数加上c需要 O(N)的时间复杂度, 现在我们只需要修改差分数组的两个数$b_l 和 b_{r+1}$就可以O(1)了

那么我们就可以得到一个公式来通过 b 数组保证 a 数组只有指定范围内会变化, 公式如下

1
2
3
4


void insert(l, r, c){
  b[l] += c;
  b[r+1] -= c;
}

假设 a 数组全部是 0, 那么差分数组 b 也就全部是 0 —- 这是我们不需要考虑构造 b 数组的关键, 我们只需要考虑插入就可以了

但是现在 a 数组不是 0, 我们可以看成是让原数组进行了 n 次加c操作进而得到了a 数组, 第一次是让数组[1,1]加上$a_1$,第二次是让原数组[2,2]区间加上 $a_2$ ,第三次是让原数组[3,3]区间间加上 $a_3$ , 一直到第 n 次是让原数组[n,n]区间加上了 $a_n$

我们知道, 要让原数组a加上c只需要在差分数组中进行 $b_l + c$ 和$b_{r+1}-c$ 即可, 那么在这里就是 $(b_1 +a_1$ && $b_2-a_1)$ 即可确定对应原数组中区间[1,1]的数, $(b_2+a_2 $ && $ b_3-a_2)$ 即可确定原数组区间[2,2]的数, 以此类推 $(b_n+a_n$ && $b_{n+1}-a_n)$原数组区间[n,n]的数.

对于原地插入, 直接调用函数 insert(1,1,a[1]); insert(2,2,a[2]); insert(3,3,a[3]); .... insert(n,n,a[n]); 即可保证能从b 数组求出前缀和

要利用 b 数组原地(空间复杂度O(1))求前缀和, 直接 $b_i = b_i+b_{i-1}$ 这样遍历后的的 b 数组直接和 a 数组的值一样了

求前缀和是一个递推过程

所以在实际使用中, 我们不需要考虑如何构造差分数组, 只需要让原数组都为 0, 然后遍历本来应插入的值, 由差分数组进行插入即可

二维差分

一维差分的作用是对一段区间加上一个值, 那么二维差分就是给某一块子矩阵加上值

对于差分矩阵 $b_{ij}$ , 对于指定的 i , j 所指向的元素加上常数 c , 其影响就是对应前缀和矩阵的 i, j 右下方所有元素都会加上常数c

所以, 我们如果想要指定前缀和矩阵 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的所有元素加上常数的话, 就要借助 b 矩阵打个补丁.

1
2
3
4
5
6


void insert(int x1, int y1, int x2, int y2, int c){
  b[x1][y1] += c;
  b[x2+1][y1] -= c;
  b[x1][y2+1] -= c;
  b[x2+1][y2+1] += c;
}

如下图

二维求前缀和的递推公式为

1

b[i][j] = b[i-1][j] + b[i][j-1] + b[i][j] - b[i-1][j-1]