题解 | #【模板】差分#

解题思路：

• 分析问题，最直观的办法是暴力，但是在数据量1E5的情况下时间复杂度是达不到要求的。

• 引入差分数组，降低时间复杂度，对于$a_1,\mathrm{.}\mathrm{.}\mathrm{.},a_{n}a\_1,...,a\_n$构造差分数组$c{f}_1,\mathrm{.}\mathrm{.}\mathrm{.},c{f}_{n}cf\_1,...,cf\_n$对于$c{f}_i=a_i-a_{i-1}cf\_i\; =\; a\_i\; -\; a\_\{i-1\}$.

• 对于每一次区间[l,r]修改v，有$c{f}_l+=v,c{f}_{r+1}-=vcf\_l\; +=\; v,\; cf\_\{r+1\}\; -=\; v$,因为当左边界加上v时，$a_l-a_{l-1}\mathrm{的}\mathrm{差}\mathrm{值}\mathrm{增}\mathrm{加}\mathrm{了}v\mathrm{，}\mathrm{而}{a}_{r+1}-a_r\mathrm{应}\mathrm{该}\mathrm{减}\mathrm{小}va\_l\; -\; a\_\{l-1\}的差值增加了v，而a\_\{r+1\}\; -\; a\_r应该减小v$ 最后只要$O(n)O(n)$就更新一遍原始数组的值，就得到了答案。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin>>n>>m;
    vector<long long> v(n+1,0);
    vector<long long> cf(n+1);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &v[i]);
        cf[i] = v[i] - v[i-1];
        
    }
    int l, r, a;
    for(int i = 0; i < m; ++i){
        scanf("%d%d%d",&l,&r,&a);
        cf[l] += a;
        if(r+1 <= n) cf[r+1] -= a; 
    }
    for(int i = 1; i < n; ++i){
        v[i] = v[i-1] + cf[i];
        cout<<v[i]<<" "; 
    }
    cout<<v[n-1]+cf[n]<<endl;
    return 0;
}