差分法

1.对于任意数组，如果要对其中某一段进行加减操作,

可以建立差分数组b[i]=a[i]-a[i-1];

2.对于在一段的开始和结尾x,y以及对这段进行的加减操作z

(b[]从b[1]开始)

b[x]=+z

b[y+1]-=z;

3.对a[]进行还原a[i]=b[i]+a[i-1],得到进行过区间加减的数组a[];

题目链接：acwing3729

#include<bits/stdc++.h>
using namespace std;
const int N=2*10e5+10;
int v[N];
int c[N];
int T,n;
int main()
{
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>v[i];
            c[i]=v[i]-v[i-1];//构建差分数组
        }
        for(int i=1;i<=n;i++) if(v[i]) c[i+1]-=1,c[max(1,i-v[i]+1)]+=1;//在i到i-v[i]+1区间进行操作
        for(int i=1;i<=n;i++)
            {
                v[i]=v[i-1]+c[i];//还原数组
                cout<<bool(v[i])<<" ";//以0，1输出
            }
        cout<<endl;
    }
}