ix. Segment Tree Merging and Splitting

Many dynamic segment trees over the same value range $[0,n)$ share one node pool. Two trees can be merged (union of multisets) and a tree can be split by value or by count. All merges together cost $O(\text{nodes ever created})$, which is $O((n+q)\log n)$. That makes this the tool for subtree aggregates on trees (an alternative to small-to-large), for “sort a range” operations, and for set unions in DSU-like processes.

Implementation

struct MergeSeg {
    int n; vector<int> L{0}, R{0}; vector<ll> c{0};     // node 0 = empty tree, never modified
    MergeSeg(int n) : n(n) {}
    int node() { L.push_back(0); R.push_back(0); c.push_back(0); return sz(c) - 1; }
    int add(int t, int v, ll d, int l, int r) {          // returns the (possibly new) root
        if (!t) t = node();
        c[t] += d;
        if (r - l > 1) {
            int m = (l + r) / 2;
            if (v < m) { int x = add(L[t], v, d, l, m); L[t] = x; }
            else { int x = add(R[t], v, d, m, r); R[t] = x; }
        }
        return t;
    }
    int add(int t, int v, ll d) { return add(t, v, d, 0, n); }
    int merge(int a, int b, int l, int r) {              // destroys b, reuses a
        if (!a || !b) return a ^ b;
        if (r - l == 1) { c[a] += c[b]; return a; }
        int m = (l + r) / 2;
        int x = merge(L[a], L[b], l, m), y = merge(R[a], R[b], m, r);
        L[a] = x; R[a] = y; c[a] = c[x] + c[y];
        return a;
    }
    int merge(int a, int b) { return merge(a, b, 0, n); }
    pair<int, int> splitCount(int t, ll k, int l, int r) {   // (k smallest, rest)
        if (!t || k <= 0) return {0, t};
        if (k >= c[t]) return {t, 0};
        int u = node();
        if (r - l == 1) { c[u] = c[t] - k; c[t] = k; return {t, u}; }
        int m = (l + r) / 2; ll left = c[L[t]];
        if (k <= left) { auto [a, b] = splitCount(L[t], k, l, m); L[t] = a; L[u] = b; R[u] = R[t]; R[t] = 0; }
        else { auto [a, b] = splitCount(R[t], k - left, m, r); R[t] = a; R[u] = b; }
        c[t] = c[L[t]] + c[R[t]]; c[u] = c[L[u]] + c[R[u]];
        return {t, u};
    }
    int kth(int t, ll k) const {                        // 0-indexed, assumes k < c[t]
        int l = 0, r = n;
        while (r - l > 1) { int m = (l + r) / 2; if (k < c[L[t]]) t = L[t], r = m; else k -= c[L[t]], t = R[t], l = m; }
        return l;
    }
};

Take returned child indices into locals before assigning (push_back may reallocate the vectors). Split by value is the same recursion as splitCount, comparing $x$ with the midpoint instead of $k$ with the left count. Never use a tree after it has been merged into another, and never merge a tree with itself.

Proof: all merges cost $O(\text{number of nodes created})$

A call merge(a, b) with both non-null visits node pair $(a,b)$ and then discards $b$ forever (its children are absorbed into $a$‘s). So each recursive call with two non-null arguments destroys one node. Calls with a null argument return immediately and are charged to their parent call (at most two per parent). The number of nodes destroyed is at most the number created, which is $O(\log n)$ per add and per split (each split creates at most one node per level). Summing gives $O((n+q)\log n)$ for any sequence of operations.

Uses

Subtree queries on a tree: give each vertex a tree over its values (colours, depths, ranks), process vertices bottom-up with root[v] = merge(root[v], root[child]), and answer $v$‘s queries right after its children are merged in, before $v$ is merged into its parent (later merges reuse its nodes). For “most frequent colour in each subtree” (CF 600E), store the max count and the sum of colours achieving it in each node, combining at the leaves of merge. $O(n\log n)$ total, often simpler than small-to-large.

Depth-indexed tree DP: “for each $v$, the number of descendants at each depth” merges trees indexed by depth. When you need the whole array per vertex, long-path decomposition is $O(n)$ instead (Long-Path Decomposition).

DSU with sets of values: merge the value trees when components merge; component queries like “$k$-th smallest in my component” become kth.

Range sort (sortable array): keep the array as runs, each run a value-tree (or binary trie over distinct keys) plus a direction flag; an outer structure (set of run starts, segment tree of run aggregates) folds runs. Sorting $[l,r)$ splits the boundary runs by count and merges all runs inside. By the merge bound the total is $O((n+q)\log n)$ amortized. With per-node folds in both key orders (forward and backward), this supports “point set, range sort, range composite” (Library Checker) with non-commutative monoids. The trie needs distinct keys to index by; break ties with $(\text{key},\text{index})$ pairs when the values repeat.

Proof: range sort is amortized $O(\log n)$ per operation

Each sort performs at most two splits, which create $O(\log n)$ nodes, and merges some number of runs into one. Every merge cost is paid by node destruction (previous proof), and the number of runs decreases by one per merged run while each operation creates at most two new runs. So the total merge work is bounded by the total nodes created, $O((n+q)\log n)$, and run bookkeeping is $O(\log n)$ per run created.

Compared with small-to-large

	Segment tree merging	Small-to-large with map
time	$O(n\log n)$ total	$O(n{\log }^{2}n)$
memory	$O(n\log n)$ nodes	$O(n)$
supports	any segment-tree aggregate over values, split, $k$-th	anything a container supports
order of queries	answer before merging upward	same