python/TangDou/AcWing/SegmentTree/P3372_Dynamic_XDS.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 5e5 + 10;

// 动态开点线段树
#define int long long
#define ls tr[u].l
#define rs tr[u].r
#define mid ((l + r) >> 1)
struct Node {
    int l, r;
    int sum, add;
} tr[N << 1];

int root, idx;
// 汇总统计信息
void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum;
}
// 创建节点：节点号分配，懒标记初始化
void build(int &u) {
    if (u) return;
    u = ++idx;
    // tr[u].add = 0;
}

void pushdown(int &u, int l, int r) {
    if (tr[u].add == 0) return; // 如果没有累加懒标记，返回
    build(ls);                  // 左儿子创建
    build(rs);                  // 右儿子创建
    // 懒标记下传
    tr[ls].sum += tr[u].add * (mid - l + 1); // 区间和增加=懒标记 乘以 区间长度
    tr[rs].sum += tr[u].add * (r - mid);
    tr[ls].add += tr[u].add; // 加法的懒标记可以叠加
    tr[rs].add += tr[u].add;
    // 清除懒标记
    tr[u].add = 0;
}

// 区间修改
void modify(int &u, int l, int r, int L, int R, int v) {
    build(u); // 动态开点

    if (l >= L && r <= R) {           // 如果区间被完整覆盖
        tr[u].add += v;               // 加法的懒标记可以叠加
        tr[u].sum += v * (r - l + 1); // 区间和增加=懒标记 乘以 区间长度
        return;
    }
    if (l > R || r < L) return; // 如果没有交集

    // 下传懒标记
    pushdown(u, l, r);
    // 分裂
    modify(ls, l, mid, L, R, v), modify(rs, mid + 1, r, L, R, v);
    // 汇总
    pushup(u);
}

// 区间查询
int query(int u, int l, int r, int L, int R) {
    if (l >= L && r <= R) return tr[u].sum; // 如果完整命中，返回我的全部
    if (l > R || r < L) return 0;           // 如果与我无关,返回0
    pushdown(u, l, r);
    return query(ls, l, mid, L, R) + query(rs, mid + 1, r, L, R);
}
/*
参考答案：
11
8
20
*/
signed main() {
#ifndef ONLINE_JUDGE
    freopen("P3372.in", "r", stdin);
#endif
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin >> n >> m; // n个节点，m次操作
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        modify(root, 1, n, i, i, x); // 单点修改,赋初值
    }

    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            int x;
            cin >> x;
            modify(root, 1, n, l, r, x); //[l,r]区间修改为x
        } else
            cout << query(root, 1, n, l, r) << endl; // 区间sum和
    }
    return 0;
}