一.简介

 差分数组是指对一个一维数组进行差分操作得到的新数组。差分操作是指计算原数组中相邻元素之间的差异，并将这些差异作为新数组的元素。

具体而言，对于一个长度为n的一维数组x，其差分数组diff的第i个元素可以通过以下公式计算得到：

diff[i] = x[i] - x[i-1]

其中，diff[0] = x[0]，因为第一个元素没有前一个元素。

差分数组的长度比原数组少1，因为差分操作会减少一个元素。差分数组中的元素表示了原数组中相邻元素之间的差异。

需要注意的是，差分数组可以通过反向操作（即累加）来恢复原始数组。这意味着，如果有原始数组的差分数组，可以通过对差分数组进行累加操作来还原原始数组。

 

---

二.差分数组的优势

当我们遇到对一个数组的一系列范围的数据反复修改时，我们可以用差分数组。但值得注意的是查询次数要少，修改次数要多，这样效果更明显

---

三.差分数组与前缀和的区别

（1）前缀和是通过sum[i]=sum[i-1]+a[i]所实现的。它可以预处理后O(1)的速度查询区间之和。但在区间和要修改，则需要树状数组等数据结构实现。

（2）差分数组是通过d[i]=a[i]-a[i-1]所实现。它可以预处理后O(1)的速度修改区间数组的数值，但在查询时要O(n)。

---

四.详细分析差分数组

（1）修改数据

 

因为要a[1]+1，则a[1]又比a[0]多了1，则d[1]+1即可。

又因为a[1]+1，a[2]+1，所以d[2]=a[2]-a[1]并不变

最后a[3]+1，d[4]=a[4]-a[3]，所以d[4]应当-1；

总结：

若 [ i , j ]+1，则 d[i]+1，d[j+1]-1；

若[ i , j ]-1，则 d[i]-1，d[j+1]+1;

---

（2）查询

 

---

 五.模板题

（1）题目

1.题目描述：给一个数组a，经过m次修改，输出数组a

2.输入：第一行有n,m，表示数组a有n个元素，经过m次修改

              第二行n个数，表示n个元素

              第i（【3，3+m】）行，每行有三个数：l,r,s表示数组下标从l到r，分别加s

3.输出：修改后的数组a

4.样例输入：

5 3
1 2 3 4 5
1 3 1
1 5 1
3 4 2

5.样例输出：3 4 7 7 6

6.数据范围：1<=n,m<1e5；

（2）参考代码 

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
inline int read(){
	int ans=0,f=1;
	char cc=getchar();
	while(cc<'0' || cc>'9'){
		if(cc=='-') f=-1;
		cc=getchar();
	}
	while(cc>='0' && cc<='9'){
		ans=(ans<<1)+(ans<<3)+(cc-'0');
		cc=getchar();
	}
	return ans*f;
}
int a[maxn],d[maxn];
int n,m;
int main(){
	cin>>n>>m;
	//O(n)
	for(int i=1;i<=n;i++) a[i]=read();
	//预处理
	for(int i=1;i<=n;i++) d[i]=a[i]-a[i-1]; 
	//O(m)
	while(m--){
		int l=read(),r=read(),s=read();
		d[l]+=s ;d[r+1]-=s;
	}
	int sum=0;
	for(int i=1;i<=n;i++){
	//	调试 
	//	cout<<d[i]<<" ";
		sum+=d[i];
		cout<<sum<<" ";
	}
	return 0;
}

六.应用

（1）题目

P1083 [NOIP2012 提高组] 借教室 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

（2）思路 

可以用二分答案实现，二分订单，再找到大范围，最后到小范围；使用差分数组，加快了修改数据的速度，再sum累计，算出a[i]的值，若小于所给的教室，就说明这以范围的订单有问题

（3）参考代码（O(nlogm)）

#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
inline int read(){
	int ans=0,f=1;
	char cc=getchar();
	while(cc<'0' || cc>'9'){
		if(cc=='-') f=-1;
		cc=getchar();
	}
	while(cc>='0' && cc<='9'){
		ans=(ans<<1)+(ans<<3)+(cc-'0');
		cc=getchar();
	}
	return ans*f;
}
int n,m;  //天，订单
int a[maxn]; //每天有的教室
int s[maxn],e[maxn],t[maxn]; //第i的订单的起，末，量 
long long d[maxn]; //差分数组 
bool f(int x){
	memset(d,0,sizeof(d));
	for(int i=1;i<=x;i++){
		d[s[i]]+=t[i]; d[e[i]+1]-=t[i];
	} 
	long long sum=0; //第i天需要的教室
	for(int i=1;i<=n;i++){
		sum+=d[i];
		if(sum>a[i]) return 1;
	}
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=m;i++){
		t[i]=read();s[i]=read();e[i]=read();
	} 
	int l=1,r=m;
	//二分答案找订单 
	int ans=0;
	if(f(m)==0){
		cout<<0;return 0;
	}
	//O(nlogm) 
	while(l<=r){
		int mid=(l+r)/2;
		if(f(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	cout<<-1<<endl<<ans<<endl;
	return 0;
}