差分应用
1.若原先数组每个数都是0,那么可以默认差分数组初始值全为0,然后我们按照题目要求直接进行处理,最后再对差分数组进行相加,即可得到原数组处理后的值
ranges是所要进行的操作的数组({l,r}范围数字+1)
ha是差分数组
l,r<100
int n=ranges.size();
vector<int>ha(n+1,0);
for(auto i:ranges)
ha[i[0]]++,ha[i[1]+1]--;
for(int i=1;i<=n;++i)
ha[i]+=ha[i-1];
2.若原数组不全为0,那么需要通过原数组相减,才得到一个差分数组;紧接着再对这个差分数组进行处理
for(int i=1;i<=n;++i)
{
cin>>a[i];
b[i]=a[i]-a[i-1]; //b[3]=a[3]-a[2] a[2]=b[1]+b[2] a[3]=b[1]+b[2]+b[3]
}
while(m--){
cin>>l>>r>>c;
b[l]+=c,b[r+1]-=c;
}
for(int i=1;i<=n;++i)
{
a[i]=a[i-1]+b[i];
cout<<a[i]<<" ";
}