当时看y总的视频,很难理解为什么要假设a,b数组全部是0,然后把a[i]插入b,就
得到了差分数组。在此写一下自己的理解。
这个操作必须是b已经是a的差分数组的前提下
例如,我们已经知道b是a的差分数组,我只想让某个a[i]加上一个数,比如只想让a[5]加上3
那我就要insert(5,5,3),这对a[5]之前和之后的数是没有影响的,并且操作之后,b仍然是a的差分数组(这是重点)
如果没有这个操作,b就不再是a的差分数组
所以我们知道,如果a[i]改变,要想让b仍然是a的差分数组,那么就要进行insert(i,i,c)操作。
为什么要让b仍然是a的差分数组?因为我们要解题嘛,所以我们要维持a,b的关系
到这里就很明朗了
由于刚开始啊a,b全都是0,b显然是a的差分数组,因为b满足a[i] = b[1] + b[2] + … +b[i] = 0
现在a不是0了,因为a[1]加上了某个数,我们要想让b仍然是a的差分数组,那么就要进行相应的改变
怎么变?就是insert(1,1,c)嘛,c是什么?就看a[1]加上了什么咯。刚开始a[1]是0嘛,后来变成了某个数,即a[1]
所以c就是a[1]嘛,于是我们进行了insert(1,1,a[1])操作,以维持a,b间的关系。
同理,当a[2],a[3]....a[n]依次改变,我们依次进行相应的操作。
所以这就是insert(i,i,a[i])的来源
#include<iostream>
using namespace std;
const int N = 1e6+5;
int a[N], b[N];
void insert(int l , int r , int x){
b[l] += x;
b[r + 1] -= x;
}
int main(){
int n , m;
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]); //这一步是改变b,使得b仍然是a的差分数组
while(m--){//这一步是主要操作,通过操作差分数组b,间接使得把a数组【l,r】里面的数全部加上c
int l, r,c;
cin>>l>>r>>c;
insert(l,r,c);
}
//差分数组b的前i项和就是a【i】
for(int i = 1; i <= n; i++) b[i] = b[i - 1] + b[i]; //把b数组前i项求和,这时候b【i】就变成了a【i】
for(int i = 1; i <= n; i++) a[i] = b[i]; //把b【i】赋给a【i】
for(int i = 1; i<=n; i++)cout<<a[i]<<" ";
return 0;
}
细节
哈哈,明白了,非常感谢
您好,我想问下
insert(i,i,a[i]); // 就是把a数组的值一 一对应插到b数组
insert(l,r,c); // 将b中[l, r]之间的每个数加上c。
b[i] += b[i - 1] //求b的前缀和 即 a序列
这样理解对吗
是可以这么理解,不过这里insert(l, r, c) 的作用应该是:b数组左端点 L 加c,右边的R+1减c,然后在求b的前缀和(即a序列)时,a序列的(L, R)每个数都加上了c,并不是将b的每个数都加了c,而是求前缀和后导致a的每个数加了c
导致a的(l, r)区间内每个数加了c