【模板】差分

难度：2星

差分模板题。如果每次操作都是 $O(n)O(n)$ 复杂度进行模拟的话，肯定会超时。

我们观察到，对于一个数组，如果让 $a[l]a[l]$ 加 $kk$ ，$a[r+1]a[r+1]$ 减 $kk$ ，做一个前缀和之后，相当于 $[l,r][l,r]$ 区间内每个数都加上了 $kk$ 。

所以我们只需要对所有的操作做如上处理（单次处理 $O(1)O(1)$ 复杂度），最后做一个前缀和就行了。

#include<bits/stdc++.h>
using namespace std;
long long a[101010],dp[101010];
int main(){
    int n,m,i;
    cin>>n>>m;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=m;i++){
        int l,r,x;
        cin>>l>>r>>x;
        dp[l]+=x;
        dp[r+1]-=x;
    }
    for(i=1;i<=n;i++)dp[i]+=dp[i-1];
    for(i=1;i<=n;i++)cout<<a[i]+dp[i]<<" ";
}