更优雅的线段树

线段树原理非常简单，但如何优雅的实现却是一个问题

¶ 线段树简介

线段树就是把一个序列原有 $n$ 个点扩充为 $n\log n$ 个点，保持一定结构进行加速

每个点有

• 自己管辖的区域
• 两个拼起来是自己的子节点（ $self = lson \cup rson$ ）
• 子节点不交（ $lson \cap rson = \varnothing$ ）
• 可以快速的区间合并

¶ 实现

个人喜欢写结构体和指针

自定义一个 null 可能是避免代码冗长的一个办法（否则到处判 == NULL ）

但是这样的话好像有些函数得分开写

查询区间 $[L,R]$ 用全局变量存可以减少参数传递

P3372 【模板】线段树 1

#include <iostream>
typedef long long ll;
const int N = 100000;

struct Node {
    ll sum, tag;
    int l, r;
    Node *ls, *rs;
    inline int len();
    void maintain();
    void pushdown();
    ll query();
    void add();
    Node *build(int, int);
    void print();
};
Node T[N * 4];
Node *null;
int cnt = 1, L, R, X;

int Node::len() { return r - l + 1; }
void Node::maintain() { sum = ls->sum + rs->sum; }
void Node::pushdown() {
    ls->tag += tag, rs->tag += tag;
    ls->sum += ls->len() * tag, rs->sum += rs->len() * tag;
    tag = 0;
    null->sum = null->tag = 0;
}
ll Node::query() {
    if (L <= l && r <= R) return sum;
    if (r < L || R < l) return 0;
    pushdown();
    return ls->query() + rs->query();
}
void Node::add() {
    if (r < L || R < l) return;
    if (L <= l && r <= R)
        tag += X, sum += len() * X;
    else
        pushdown(), ls->add(), rs->add(), maintain();
}
Node *Node::build(int l, int r) {
    Node *ret = &T[cnt++];
    ret->l = l, ret->r = r, ret->ls = ret->rs = null;
    if (l == r)
        cin >> ret->sum;
    else {
        int mid = (l + r) / 2;
        ret->ls = build(l, mid), ret->rs = build(mid + 1, r);
        ret->maintain();
    }
    return ret;
}

void Node::print() {
    if (this == null) return;
    cerr << l << ' ' << r << ' ' << sum << ' ' << tag << endl;
    ls->print(), rs->print();
}

int main() {
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n, m;
    null = T;
    null->ls = null->rs = null;
    cin >> n >> m;
    Node *rt = null->build(1, n);
    L = 1, R = n;
    while (m--) {
        int opt;
        cin >> opt >> L >> R;
        if (opt == 1) {
            cin >> X;
            rt->add();
        } else
            cout << rt->query() << '\n';
    }
    return 0;
}