差分及二维差分_差分和二维差分

差分

差分即相邻两个数的差，给定数组$a$我们能得到其差分数组$d[i]=a[i]-a[i-1],a[0]=0$。

差分和前缀和的区别

前缀和求的是$sum[i]={\sum }_{j=1}^{i}a[j]$，如果使用前缀和表示某个位置的元素，那么$a[i]=sum[i]-sum[i-1]$。对比差分，我们发现差分和前缀和在预处理和求和的运算刚好是“相逆”的。

区间加法

对于某个位置的差分，影响的是后面所有元素的值(前缀和)，而不影响它前面元素的值(前缀和)。

那么我们会发现，如果对一个区间$[x,y]$内的所有数都加上一个数$p$，那么显然只有$d[x]$和$d[y+1]$的需要改变：

int a[maxn], d[maxn];

void add(int x, int y, int p) {
	d[x] += p;
	d[y + 1] -= p;
}
1
2
3
4
5
6

差分数组求得原数组

不难得知$a[i]={\sum }_{j=1}^{i}d[j]$。

二维差分

前缀和可以衍生到二维前缀和，那么差分也有二维差分，对于如下矩阵，需要类似二维前缀和的求法来求差分矩阵：

$$\begin{gathered} 123 \\ 456 \\ 798 \end{gathered}$$

差分矩阵为：

$$\begin{gathered} 111 \\ 300 \\ 31-2 \end{gathered}$$

而对于原矩阵某个位置的值，等价于以这个元素为右下角，原矩阵左上角为左上角的子矩阵中所有元素的和：（原矩阵蓝色方块的值由红色区域加上蓝色方块的差分值求和得到）

int a[N][N], d[N][N];

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		cin >> a[i][j];
		d[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
		//前缀和：sum[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
	}
}
1
2
3
4
5
6
7
8
9

子矩阵加法

差分矩阵改变一个数影响的是以该元素为左上角，原矩阵的右下角$(n,m)$为右下角形成子矩阵区域。

类似于一维差分，二维差分可以进行快速子矩阵加法，当我们需要对如下的红色区域加上一个数$p$时，只需要$d[1][1]+p$：

产生的影响为整个矩阵，为了消除其他位置的影响，我们需要将上图白色区域的影响消除，也就是要更新$d[3][1],d[1][3],d[3][3]$，蓝色区域需要减去$p$即绿色位置减去$p$，而黄色区域多减了，需要再加上$p$，即所有紫色区域加上$p$：

void add(int i, int j, int x, int y, int val) {
    d[i][j] += val, d[x + 1][y + 1] += val;
    d[x + 1][j] -= val, d[i][y + 1] -= val;
}
1
2
3
4

差分矩阵求得原矩阵

类似于一维差分，当我们需要求得原矩阵时，不可能对于每一个元素和左上角形成的子矩阵求和，这样太麻烦了，实际上我们可以使用二维循环，对于第一列，手算一下不难得出是正确的，然后对于每个元素左上角$2\times 2$的子矩阵，除了当前元素的位置其余三个位置都是原矩阵的元素，那么我们对上述求差分的过程反着来：

$a[i][j]=d[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1]\iff a^{\prime }[i][j]=d[i][j]+d[i-1][j]+d[i][j-1]-d[i-1][j-1]$

这样当我们对差分矩阵动态修改之后就可以$O(nm)$得到新的矩阵了

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		d[i][j] = d[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
    }
}
1
2
3
4
5