树具有天然的合并性质，即某节点的子树信息全部来自于它子节点的子树信息。因此先计算子节点，再计算父节点，在树上 DFS 的过程中，将子树的信息合并到父节点上。

线段树合并暂时不支持区间修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
template<class info>
struct SMT {
    int L, R, pcnt;
    vector<info> t;
    vector<int> ls, rs;
    vector<int> rt;

    SMT() {
        init(0, 0);
        t.resize(N << 2);
        ls.resize(N << 2);
        rs.resize(N << 2);
    }

    void init(int l, int r) {
        L = l, R = r;
        pcnt = 0;
        rt.assign(N, 0);
    }

    void init(int p) {
        t[p] = info();
        ls[p] = rs[p] = 0;
    }

#define mid ((L+R)>>1)
#define len (R-L)
#define lson ls[p],L,mid
#define rson rs[p],mid,R

    void push_up(int& p) {
        t[p] = t[ls[p]] + t[rs[p]];
    }

    void modify(int x, const info& d, int& p, int L, int R) {
        if (!p) p = ++pcnt, init(p);
        if (R - L < 2) return t[p].apply(d);
        if (x < mid) modify(x, d, lson);
        else modify(x, d, rson);
        return push_up(p);
    }
    void modify(int x, const info& d, int p) {
        modify(x, d, rt[p], L, R);
    }

    info query(int l, int r, int& p, int L, int R) {
        if (l <= L && R <= r) return t[p];
        info res = info();
        if (l < mid) res = res + query(l, r, lson);
        if (mid < r) res = res + query(l, r, rson);
        return res;
    }
    info query(int l, int r, int& p) {
        return query(l, r, rt[p], L, R);
    }

    void merge(int& q, int& p, int L, int R) {
        if (!q || !p) return q |= p, void();
        if (R - L < 2) return t[q].apply(t[p]);
        merge(ls[q], lson);
        merge(rs[q], rson);
        return push_up(q);
    }
    void merge(int& q, int& p) {
        return merge(rt[q], rt[p], L, R);
    }
};

边合并边计算答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<class info>
struct SMT {
    // ...

    void merge(auto& res, int& q, int& p, int L, int R);
    void merge(auto& res, int& q, int& p) {
        return merge(res, rt[q], rt[p], L, R);
    }
};

struct info {
    void apply(const info& d) {}
    friend info operator + (const info& l, const info& r) {}
};

template<class info>
void SMT<info>::merge(auto& res, int& q, int& p, int cl, int cr) {
    if (!q || !p) return q |= p, void();
    if (cl == cr) return t[q].apply(t[p]);
    merge(res, ls[q], lson);
    merge(res, rs[q], rson);
    return push_up(q);
}