如下:
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];
始终要记得,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;
#include[HTML_REMOVED]
using namespace std;
const int N=100100;
int a[N],b[N];
void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;//其实是假定a数组最开始都是0,
//那么b数组初始时就是a数组的差分数组了,对于每一个a[i],相当于插入了一个数,可以直接调用insert函数即可。
//例如 a = [1, 2, 2, 1, 2, 1] b = [0, 0, 0, 0, 0, 0]
//insert(1,1,a[1])
//b[1] += 0 + 1 => 1
//b[2] -= 0 + 1 => -1
//insert(2,2,a[2])
//b[2] += -1 + 2 => 1
//b[3] -= 0 + 2 => -2
}
int main()
{
int m,n;
scanf(“%d%d”,&m,&n);
for(int i=1;i<=m;i)
{
scanf(“%d”,&a[i]);
insert(i,i,a[i]);//差分每个下标少掉的数是上一个下标的数
}
while(n–)
{
int l,r,d;
cin>>l>>r>>d;
insert(l,r,d);
}
for(int i=1;i<=m;i)
{
b[i]+=b[i-1];//l每移动一次;在r+1之前的数都必须少掉一个c,那么b[1]加多少,b[2]变少相应那么多;加上之前的便是少掉b[1]
printf(“%d “,b[i]);
}
return 0;
}