题解 | 【模板】差分

如果每一次操作都直接操作原数组，在极端情况下达到O(n^2)导致超时。

采用差分思想进行数组操作：

实现一个差分数组，该数组的元素置零，该数组用来表示多个patch区间，区间头为差分数，区间末尾为-差分数。

维护cnt表示当前patch大小，最后一次性加到原数组里。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,q,l,r,d;
    cin>>n>>q;
    vector<long long> v(n);
    vector<long long> b(n,0);
    for(int i=0;i<n;++i){
        cin>>v[i];
    }
    for(int i=0;i<q;++i){
        cin>>l>>r>>d;
        b[l-1]+=d;
        b[r]-=d;
    }
    long long cnt=0;
    for(int i=0;i<n;++i){
        cnt+=b[i];
        cout<<v[i]+cnt<<" ";
    }
}