题解 | 【模板】差分

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define LCHILD(p) (((p) << 1) | 1)
#define RCHILD(P) (((p) + 1) << 1)
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    struct node {
        int field;
        int lazy;
    };
    vector<struct node> st(4 * n);
    auto pushdown = [&](int p, int left, int right) -> void {
        if (st[p].lazy == 0)
            return;
        int mid = (left + right) >> 1;
        st[LCHILD(p)].field += st[p].lazy * (mid - left + 1);
        st[LCHILD(p)].lazy += st[p].lazy;
        st[RCHILD(p)].field += st[p].lazy * (right - mid);
        st[RCHILD(p)].lazy += st[p].lazy;
        st[p].lazy = 0;
    };
    auto pushup = [&](int p) -> void {
        st[p].field = st[LCHILD(p)].field + st[RCHILD(p)].field;
    };
    auto build = [&](auto&& build, int p, int left, int right) -> void {
        st[p].lazy = 0;
        if (left == right) {
            st[p].field = data[left];
            return;
        }
        int mid = (left + right) >> 1;
        build(build, LCHILD(p), left, mid);
        build(build, RCHILD(p), mid + 1, right);
        pushup(p);
    };
    auto query = [&](auto&& query, int p, int left, int right, int qleft,
    int qright) -> int {
        if (left > qright || right < qleft)
            return 0;
        if (left >= qleft && right <= qright)
            return st[p].field;
        int mid = (left + right) >> 1;
        pushdown(p, left, right);
        int q1 = query(query, LCHILD(p), left, mid, qleft, qright);
        int q2 = query(query, RCHILD(p), mid + 1, right, qleft, qright);
        return q1 + q2;
    };
    auto update = [&](auto&& update, int p, int left, int right, int qleft,
    int qright, int val) -> void {
        if (qleft > right || left > qright)
            return;
        if (left >= qleft && right <= qright) {
            st[p].field += val * (right - left + 1);
            st[p].lazy += val;
            return;
        }
        int mid = (left + right) >> 1;
        pushdown(p, left, right);
        update(update, LCHILD(p), left, mid, qleft, qright, val);
        update(update, RCHILD(p), mid + 1, right, qleft, qright, val);
        pushup(p);
    };
    build(build, 0, 0, n - 1);
    for (int i = 0; i < k; i++) {
            int l, r, v;
            cin >> l >> r >> v;
            update(update, 0, 0, n - 1, l - 1, r - 1, v);
    }
    for(int i=0;i<n;i++)
    {
        cout<<query(query,0,0,n-1,i,i)<<' ';
    }
}

signed main() {
    int t = 1;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    while (t--) {
        solve();
    }
    return 0;
}

此题是道差分的板子题，但我搞不明白差分的原理，用线段树写了一下，需要注意是区间更新时要加上懒标记，防止复杂度退化，于是这道题就成了线段树的板子题