描述

给一个长度为$nn$的数组$aa$，$mm$次操作，每次将区间$[l,r][l,r]$加$kk$，问$mm$次操作后的数组

思路

• 差分模板题，由于仅有一次查询，因此可以利用前缀和的性质，设数组$sumsum$表示$mm$次操作后，每个位置增加的数为多少，则每次操作将$sum[l]+ksum[l]+k$，$sum[r+1]-ksum[r+1]-k$，最后对数组$sumsum$求前缀和

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
ll sum[MAXN],a[MAXN];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    while(m--)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        sum[l]+=k;
        sum[r+1]-=k;
    }
    for(int i=1;i<=n;i++)
        sum[i]+=sum[i-1];
    for(int i=1;i<=n;i++)
        printf("%lld ",a[i]+sum[i]);
    puts("");
}

时间复杂度$O(n)O(n)$，空间复杂度$O(n)O(n)$