本文共 1260 字，大约阅读时间需要 4 分钟。

差分就是将数列中的每一项分别与前一项数做差。

首先一个数组 ：1 2 5 4 7 3

那么差分之后 ：1 1 3 -1 3 -4 -3

其实就是 a[i]=a[i]+a[i−1] 

得到的差分序列第一个数和原来的第一个数一样（相当于第一个数减0），

差分序列最后比原序列多一个数（相当于0减最后一个数）。

差分其实就是前缀和的逆运算；

给你一个数组a[5]={1，2，3， 4，5}；差分数组b[5]={1，1，1，1，1}；显然差分数组b[i]=a[i]-a[i-1];

那么我们可以推出，a[1]=b[1],a[2]=b[1]+b[2],…;b[i]的前缀和等于a[i],这也是为什么说差分就是前缀和的逆运算；

给出 n 个数，再给出 m 个询问，每个询问给出 l，r，x，要求你在 l 到 r 上每一个值都加上 x，输出这个序列，或者问某一个位置上的值是多少。

而只给你 O(n) 的时间范围，怎么办？

如果暴力，时间复杂度就是 O(n^2)

如果线段树或者树状数组，时间复杂度就是 O(mlogn)

所以这里用差分，时间复杂度就是 O(n)

具体操作：

先另外开一个专门差分的数组

假如在 l~r 的区间上加上 5，那我们在差分数组中的 3 位置上加上一个 5 （模拟一遍），再在8+1的位置上减一个5,如此操作完 m 次

接着运用公式 a[i]=a[i]+a[i−1] 遍历一遍数组。那么会发现在 l~r 的区间上，已经使差分数组全部加上了 5 。

例题：

题目：

输入一个长度为n的整数序列。

接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。

输入格式

第二行包含n个整数，表示整数序列。

接下来m行，每行包含三个整数l，r，c，表示一个操作。

输出格式

#include
   
    using namespace std;const int N=100100;int a[N],b[N];int n,m;void insert(int l,int r,int p){	b[l]+=p;	b[r+1]-=p;}int main(){	ios::sync_with_stdio(false);	cin>>n>>m;	for(int i=1;i<=n;i++)        cin>>a[i];	for(int i=1;i<=n;i++)         insert(i,i,a[i]);//建立差分数组	while(m--){		int l,r,c;		cin>>l>>r>>c;		insert(l,r,c);	}	for(int i=1;i<=n;i++) 	b[i]+=b[i-1];   //要求的数列就是差分数组的前缀和	for(int i=1;i<=n;i++) 	cout<
    
     <<" ";	cout<
    
   

转载地址：http://gvyzi.baihongyu.com/