差分数组原理

前言

考虑这么一个问题：让一个区间内的所有数同时加、减、乘、除上同一个数，这是一种很常见的操作。

而对于这操作，最简单的做法就是用循环逐一对区间内所有数进行操作。这种方法的时间复杂度是O(n)。

但是若数据量级达到百万千万级别以上，频繁的进行区间修改的话，**O(n)**复杂度还是太慢了。

而对于一组不会发生增删节点的离线数据来说，差分数组是区间修改的最优选择。

原理

差分，其实可以看成前缀和的一种逆运算。即：

$b[i]=a[i]-a[i-1]$

其中a[i]为原数组(你也可以把它看成前缀和数组)，**b[i]**为差分数组。

我们知道前缀和的公式是

$a[i]=b[i]+a[i-1]$

所以若对b[i]进行修改，那么包括位置i以后的所有前缀和都会发生相同变化。

a[n]	1	2	3	4	5
（1）	b[1]	b[1]+b[2]	b[1]+b[2]+b[3]	b[1]+b[2]+b[3]+b[4]	b[1]+b[2]+b[3]+b[4]+b[5]
（2）		b[1]+(b[2]+c)	b[1]+(b[2]+c)+b[3]	b[1]+(b[2]+c)+b[3]+b[4]	b[1]+(b[2]+c)+b[3]+b[4]+b[5]
（3）				b[1]+(b[2]+c)+b[3]+(b[4]-c)	b[1]+(b[2]+c)+b[3]+(b[4]-c)+b[5]
（4）	b[1]	b[1]+(b[2]+c)	b[1]+(b[2]+c)+b[3]	b[1]+b[2]+b[3]+b[4]	b[1]+b[2]+b[3]+b[4]+b[5]

如上表（2）所示，b[2]加上了一个常数c，前缀和数组a[2,3,4,5]都加上了c。

而(3)中对b[4]减去了c，所以a[4]往后的前缀和都减去了c。

得到了（4），只修改了a[2]、a[3]的效果。即让a[2,3]+c。

因此若需要多次指定不同区间进行操作，使用差分可以实现**时间复杂度O(1)**的单次修改区间。

但，如果每次修改完区间都需要实时反馈，那暴力显然是比差分数组更优的策略。想在暴力上再进行优化的话就只能用线段树or树状数组了。

代码

/*
	模板题：https://www.acwing.com/problem/content/799/
*/
#include<iostream>
using namespace std;
const int N=100010;
int a[N],b[N];
void insert(int l,int r,int c){
	b[l]+=c;
	b[r+1]-=c;
}
int main(){
	int n,m;
	cin>>n>>m;
	//读取数组、建立差分数组b[n] 
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		insert(i,i,a[i]);
	}
	//每次修改区间值，即m次修改差分数组b 
	while(m--){
		int l,r,c;
		scanf("%d%d%d",&l,&r,&c);
		insert(l,r,c);
	}
	//利用差分数组求前缀和，即求原数组 
	for(int i=1;i<=n;i++){
		a[i]=a[i-1]+b[i];
		printf("%d ",a[i]);
	}
	return 0;
}

同理可写出：二维差分数组。

/*
	模板题：https://www.acwing.com/problem/content/800/
*/
#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],temp[N][N]; 
void insert(int x1,int y1,int x2,int y2,int c){
	temp[x1][y1]+=c;
	temp[x2+1][y1]-=c;
	temp[x1][y2+1]-=c;
	temp[x2+1][y2+1]+=c;
}
int main(){
	int n,m,q;
	cin>>n>>m>>q;
	//建立差分数组 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			insert(i,j,i,j,a[i][j]);
			/*
				因插入时是一点，可以看做：
					x1、x2融合 
					y1、y2融合 
			*/ 
		}
	
	//对差分矩阵修改 
	while(q--){
		int x1,y1,x2,y2,c;
		cin>>x1>>y1>>x2>>y2>>c;
		insert(x1,y1,x2,y2,c); 
	}
	
	//重建前缀和矩阵，即求原数组 
	for(int i=1;i<=n;i++){ 
		for(int j=1;j<=m;j++){
			a[i][j]=temp[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
			cout<<a[i][j]<<" ";
		}
		cout<<endl; 
	} 
	return 0;
}

小结

利用差分数组修改区间需要创建差分数组、重建前缀和数组(即原数组)两个过程。

因此少次的区间修改时，效率上并不比直接使用循环要高，所以对离线数列区间修改时，应注意相关的使用场景。