题解 | 【模板】差分

#include <iostream>
using namespace std;
#include<vector>
#include<algorithm>
#define int long long 
#define N 1e6
//差分数组为 diff[i]=a[i]-a[i-1]
//当对差分数组进行前缀和 例如prefix[3]=a[1]+a[2]-a[1]+a[3]-a[2]=a[3]    prefix[i]的值就是a[i]
//    差分数组增减后 再进行前缀和 常用于对区间的更改:
//当diff[i]++ 例如对diff[2]++ 则prefix[3]=a[1]+(a[2]-a[1]+1)+a[3]-a[2]=a[3]+1   
//                             prefix[2]=a[1]+(a[2]-a[1]+1)          =a[2]+1 
//所以diff[i]++  就是对包括i区间之后的所有值进行了++   操作后需要及时进行前缀和更新！！

signed main() {
    int n,m;
    cin>>n>>m;
    vector<int>a(N);//原数组
    vector<int>diff(N);//差分数组
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    //创建差分数组
    for(int i=1;i<=n;i++){
         diff[i]=a[i]-a[i-1];
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
     //对差分数组进行修改  实现区间更改 
       diff[l]+=k;
       diff[r+1]-=k;
    }
    //差分数组进行前缀和 结果得到原数组
        for(int i=1;i<=n;i++){
             a[i]=a[i-1]+diff[i];
        }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }

}
// 64 位输出请用 printf("%lld")