一、差分：一维数组的差分可看作是一维数组前缀和的逆运算。

二、差分数组

首先给定一个原数组a:   a[1]、a[2]、a[3]、......

然后构造一个数组b: b[1]、b[2]、b[3]....

使得a[i]=b[1]+b[2]+b[3]+b[4]+.....b[i]。

那么根据上一节讲的，a数组就是b数组的前缀和数组。 

也就是说，a数组就是b数组的前缀和数组，反过来，我们把b数组叫做a数组的差分数组。话句话说，每一个a[i]数组都是b数组中从头开始的一段区间和。

三、功能及作用

    给区间[L,R]中每个数加上 c:  B[L] +=c， B[R+1] -=c

四、构造

考虑如何构造差分数组b：

最为直接的方法：

a[0]=0  b[1]=a[1]-a[0];  b[2]=a[2]-a[1];  b[3]=a[3]-a[2];  ......  b[n]=a[n]-a[n-1];

五、应用

【问题描述】给定区间[L,R]，让我们把a数组中的[L,R]区间中的每一个数都加上c， 即a[L]+c,  a[L+1]+c,  a[L+2]=c , ....  a[R]+c

解法一：暴力解法

用for循环，从L到R区间，时间复杂度O（n），如果我们需要对原数组执行m次这样的操作，那么时间复杂度就会变成O(n*m)。

解法二：差分

始终要记住一点：a数组是b数组的前缀和数组。比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。

首先让差分b数组中的b[L]+c，通过前缀和运算，a数组变成a[L]+c,... a[L+1]+c,.... a[n]+c

然后我们打个补丁， b[R+1] -c ，通过前缀和运算， a数组变成 a[R+1]-c,  ...  a[R+2]-c, ...   a[n] -c, ...

图解过程：

b[L]+c, 效果使得a数组中a[L]及以后的数都加上了c(红色部分)，但是我们只要求L到R区间加上c，因此还需要执行b[R+1]-c， 让a数组中a[R+1]以及往后的区间再减去c(绿色部分)，这样对于a[r]以后区间的数组相当于没有发生改变。

结论：给a数组中的[L,R]区间中的每一个数加上c。只需要对差分数组b做b[L]+=c，b[R+]-=c，时间复杂度为O（1）。

如果上面的描述不够清楚，我们可以借助下面方式来表示，我们假设a数组是原始数组，b数组是差分数组。我们的目的是让a数组的某个区间段加上一个数c。初始状态如下：

需求1：我们要将[1,4]范围内所有的数都加上3

规律：当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的右端点的后一个值则会相反地变化。

那么用代码表示：

while(t--){//操作次数  	cin>>x>>y>>change;//左右端点值   	cin>>c;//c是每次加减的值   	b[x]=b[x]+c;  	b[y+1]=b[y+1]-c;  }

那么能不能反过来求a[i]呢，因为b数组是差分数组，满足公式b[i]=a[i]-a[i-1]

那么a[i]=a[i-1]+b[i]

六、题目

【题目描述】

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

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

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

【输入描述】

第一行包含两个整数n和m。

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

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

【输出描述】

共一行，包含n个整数，表示最终序列。

【样例输入】

6 3  1 2 2 1 2 1  1 3 1  3 5 1  1 6 1

【样例输出】

3 4 5 3 4 2

【数据范围】

1≤n,m≤100000,

1≤l≤r≤n,

−1000≤c≤1000,

−1000≤整数序列中元素的值≤1000

【参考答案】

#include<iostream>  using namespace std;  const int N=1e5+10;  int a[N],b[N];   int main()  {      int n,m;      scanf("%d%d",&n,&m);      for(int i=1;i<=n;i++)       {          scanf("%d",&a[i]);          b[i]=a[i]-a[i-1];      //构建差分数组      }      int l,r,c;      while(m--)      {          scanf("%d%d%d",&l,&r,&c);          b[l]+=c;     //表示将序列中[l, r]之间的每个数加上c          b[r+1]-=c;      }      for(int i=1;i<=n;i++)       {          b[i]+=b[i-1];  //求前缀和运算          printf("%d ",b[i]);      }      return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});