Y总思路
不用考虑差分数组形式, 将原数组看作全0的数组,从而差分数组也是全0数组。
对原数组进行某种操作(插入值,即执行+c加法)达到对原数组+c的效果。
精髓、细品:插入值的时候会对差分数组b[i]进行操作(b[l]+c,b[r+1]-c),所以,初始化以及在指定区间[l,r]+c步骤后,b[i]就是满足原数组以及+c操作后的差分数组了
- 初始化:区间[i,i]+c,相当于对全0数组插入原来数组的值
- 区间[l,r]+c
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],b[N];
int n,m;
void add(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
//初始化:区间[i,i]+c
for(int i=1;i<=n;i++)add(i,i,a[i]);
//区间[i,j]+c
while(m--){
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
add(l,r,c);
}
//对差分数组执行前缀和得到原数组
for(int i=1;i<=n;i++)b[i]+=b[i-1];
for(int i=1;i<=n;i++)printf("%s%d",i==1?"":" ",b[i]);
}
思路二
将原数组看作前缀和:
1. 得到差分数组
2. 对差分数组进行操作实现原数组+c
3. 重新计算差分数组前缀和得到原数组
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],b[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
//得到差分数组
for(int i=1;i<=n;i++)b[i] = a[i] - a[i-1];
while(m--){
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
b[l]+=c;
b[r+1]-=c;
}
//得到原数列
for(int i=1;i<=n;i++)b[i]+=b[i-1];
for(int i=1;i<=n;i++)printf("%s%d",i==1 ?"":" ",b[i]);
}