题解 | 【模板】差分

无论前缀和还是差分法，目的都是为了尽可能不要出现双重循环，通过数学技巧降低时间复杂度。

前缀和：计算l，r区间内的元素和，第一反应是使用循环累加区间内的每个元素，

而前缀和则牺牲空间创建summ(n+1)数组，在得到元素值时顺便记录前缀和，将累加区间元素的循环降维成summ[r]-summ[l] 一句代码，时间复杂度从循环直接变成常数；

差分：将l，r区间内元素都加上k，第一反应同样是使用循环遍历区间内的每个元素进行变化，

而差分则是牺牲空间创建d(n+2)数组，在得到元素值时顺便记录差值，将改变区间元素的循环降维成d[r+1]-=k,d[l]+=k两句话，时间复杂度从循环直接变成常数。

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> s(n+1);
    vector<long long> d(n+2,0); // n+2：假如r=n，那么d[r+1]=n+2，防止越界
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        d[i] = s[i] - s[i-1];
    }
    while (m--) {
        long long l, r, k;
        cin >> l >> r >> k;
        d[l] += k;
        d[r+1] -= k;
    }
    for (int i = 1; i <= n; i++) {
        s[i] = s[i-1] + d[i];
        cout << s[i] << " ";
    }
}