差分数组原理及其应用

差分数组原理及其应用

前言：

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

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

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

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

原理：

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

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

我们知道前缀和的公式是

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

如上图（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)的单次修改区间。

代码

/*
	模板题：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;
}

小结

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

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

差分数组原理及其应用

原文：https://www.cnblogs.com/yifeianyi/p/13069055.html