【模板】线段树 1.5(Dynamic Segment Tree) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

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

struct Node {
    int lc = 0, rc = 0;
    unsigned long long sum = 0;
    unsigned long long tag = 0;
};

vector<Node> tr;

void update(int& u, long long L, long long R, long long ql, long long qr, unsigned long long k) {
    if (!u) {
        u = (int)tr.size();
        tr.push_back(Node());
    }
    long long ovL = max(L, ql), ovR = min(R, qr);
    tr[u].sum += k * (unsigned long long)(ovR - ovL + 1);
    if (ql <= L && R <= qr) {
        tr[u].tag += k;
        return;
    }
    long long mid = (L + R) >> 1;
    if (ql <= mid) {
        int lc = tr[u].lc;
        update(lc, L, mid, ql, qr, k);
        tr[u].lc = lc;
    }
    if (qr > mid) {
        int rc = tr[u].rc;
        update(rc, mid + 1, R, ql, qr, k);
        tr[u].rc = rc;
    }
}

unsigned long long query(int u, long long L, long long R, long long ql, long long qr, unsigned long long tagSum) {
    long long ovL = max(L, ql), ovR = min(R, qr);
    if (!u) {
        return tagSum * (unsigned long long)(ovR - ovL + 1);
    }
    if (ql <= L && R <= qr) {
        return tr[u].sum + tagSum * (unsigned long long)(R - L + 1);
    }
    long long mid = (L + R) >> 1;
    unsigned long long res = 0;
    if (ql <= mid) res += query(tr[u].lc, L, mid, ql, qr, tagSum + tr[u].tag);
    if (qr > mid) res += query(tr[u].rc, mid + 1, R, ql, qr, tagSum + tr[u].tag);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    int m;
    if (!(cin >> n >> m)) return 0;
    tr.reserve(6000000);
    tr.push_back(Node());
    int root = 0;
    for (int i = 0; i < m; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            long long l, r;
            unsigned long long k;
            cin >> l >> r >> k;
            update(root, 1, n, l, r, k);
        } else {
            long long l, r;
            cin >> l >> r;
            unsigned long long base = (unsigned long long)(l + r) * (unsigned long long)(r - l + 1) / 2ULL;
            unsigned long long extra = query(root, 1, n, l, r, 0);
            cout << base + extra << "\n";
        }
    }
    return 0;
}