差分数组详解，一维二维差分

差分数组

引言

如果给你一个包含500个元素的数组，让你把从第一个元素到第100个元素的值都加上1，你会毫不犹豫的说枚举！那么如果给你一个包含5000万个元素的数组，让你把从第一个元素到第1000万个元素的值都加上1，你会怎么做?

此时你应该怎么做？如果再说暴力枚举的话，那么可就有点太繁重了。为了解决这类进行大区间相同操作，我们有一种较好的解决方案–差分数组。

差分数组的定义

差分数组是在原数组的基础上加以魔改的。给定数组arr，我们定义数组diff，其中

i=0 , diff[ i ] = arr[ 0 ]
i >= 1 , diff[ i ] = arr[ i ] - arr[i - 1]

我们把原来数组的每个位置上的元素和前一个元素作差得到的新数组称为差分数组(difference array)，差分数组本质上就是前缀和的逆运算。

但这跟我们要解决的大区间相同操作问题又有什么关系呢？

我们先来分析差分数组的特点，diff[ i ] = arr[ i ] - arr[ i - 1 ]，那么我们如果要求arr[ i ]不就是从第0个元素一直累加到第i - 1个元素吗？

假如我们有如下数组arr[] = {2，3，6，7，11，12，15，14，9}

我们要求把下标4–8的元素都加上1，我们发现即然第i个元素是下标0到i累加的结果，那么我们如果给第0个元素加上1，就能满足区间0到i上的元素全都加1，同样的如果我们要把区间4-8的元素都加1，我们只需要把下标4及之后的加1，下标9及之后的减一即可

如图

我们发现下标4到9的diff值推算出来的原arr值都完成了加1

如果我们还想实现随机读取arr值的操作，可以再增添一个前缀和数组

一维差分数组代码实现

二维差分数组

我们是否可以实现一个二分差分数组从而实现对于矩阵内的元素快速修改呢？

答案是，当然可以。

当然这需要你对二维前缀和有所了解：见：前缀和详解，朴素前缀和，前缀和变形，二维前缀和-CSDN博客

了解了二维前缀和后，我们知道对于左上角[0,0]右下角[i,j]的前缀和有：

注意sum[i+1][j+1]为左上角[0][0]到右下角[i][j]的和
$$sum[i+1][j+1]=sum[i+1][j]+sum[i][j+1]-sum[i][j]+grid[i][j].$$
我们一维差分中有如下初始化：

i=0 , diff[ i ] = arr[ 0 ]

i >= 1 , diff[ i ] = arr[ i ] - arr[i - 1]

实际上我们不需要这样初始化，只需要将差分数组diff初始化0，在diff上区间修改，查询arr[i]就返回arr[i] + presum(diff[i])即可

由于利用差分数组查询

那么对于我们二维差分来讲，我们开一个差分矩阵diff[][]，当我们对矩阵grid[i][j]左上角[x][y]到右下角[i][j]的元素区间加上k时，结合我们的二维前缀和公式，应该对diff做如下操作：
$$\begin{gathered} diff[x][y]+=k; \\ diff[x][j+1]-=k; \\ diff[i+1][y]-=k; \\ diff[i+1][j+1]+=k; \end{gathered}$$
对于这个公式又有什么含义呢？

diff[x][y]+=k造成的影响是矩阵grid从左上[x][y]到右下[m-1][n-1]的元素都会加上k，因为我们求grid[i][j]时需要求diff的前缀和

但是我们只希望左上角[x][y]到右下角[i][j]的元素区间加上k时，所以第2、3行的含义为

令左上角[x][j+1]到右下角[m-1][n-1]都减去k，令左上角[x+1][j]到右下角[m-1][n-1]都减去k

此时左上角[i+1][j+1]到右下角[m-1][n-1]状态是加了一次k减了两次k，其余区间修改都达到预期，所以我们第四行

令左上角[i+1][j+1]到右下角[m-1][n-1]都加上k就保证了区间修改只涉及左上角[x][y]到右下角[i][j]

二维差分数组代码实现

前面说了，我们差分数组只需要开一个数组维护修改值，查询矩阵值的时候用修改值前缀和加上原值即可，所以diff初始为0

同时为了前缀和计算没有区间越界，我们开diff时开(m + 2) * (n + 2)大小（mn为原矩阵行列数目）

由于题目一般涉及到对二位差分求前缀和操作的时候一般都是离线算法，所以我们只给出求diff前缀和的代码

代码如下：

void update(int x , int y , int i  , int j , int k)
{
    diff[x + 1][y + 1]+=k;
    diff[i + 2][y + 1]-=k;
    diff[x + 1][j + 2]-=k;
    diff[i + 2][j + 2]+=k;
}
void presum()//处理前缀和
{
	for(int i = 0 ; i < m ; i++)
		for(int j = 0 ; j < n ; j++){
                diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j];
}

总结

通过差分数组我们可以快速实现区间相同操作，只需要改变区间左端点和右端点的下一个位置即可

差分数组常用于区间修改、离线查询等情况

OJ练习

1109. 航班预订统计
2406. 将区间分为最少组数
2381. 字母移位 II
2772. 使数组中的所有元素都等于零
2528. 最大化城市的最小供电站数目
2132.用邮票贴满网格图