Dynamic Segment Tree Merging

Combining two dynamically allocated segment trees enables efficient aggregation of information across disjoint sets or hierarchical structures. The operation recursively merges corresponding nodes from both trees. When one subtree is empty, the non-empty counterpart is returned immediately. At leaf nodes, values are aggregated based on problem-specific rules, such as summation or maximum comparison. The amortized complexity remains $O(N \log N)$ because each merge reduces the total node count, and the initial node pool across all trees is bounded by $O(N \log N)$.

This approach is highly effective for offline subtree queries and tree-difference array applications, where path updates are converted into point updates that are later aggregated bottom-up.

#include <cstdio>
#include <algorithm>

struct SegNode {
    int max_freq = 0;
    int best_id = 0;
    SegNode *l = nullptr;
    SegNode *r = nullptr;
};

SegNode* merge_trees(SegNode* a, SegNode* b, int low, int high) {
    if (!a) return b;
    if (!b) return a;
    if (low == high) {
        a->max_freq += b->max_freq;
        return a;
    }
    int mid = (low + high) >> 1;
    a->l = merge_trees(a->l, b->l, low, mid);
    a->r = merge_trees(a->r, b->r, mid + 1, high);
    if (a->r->max_freq > a->l->max_freq) {
        a->max_freq = a->r->max_freq;
        a->best_id = a->r->best_id;
    } else {
        a->max_freq = a->l->max_freq;
        a->best_id = a->l->best_id;
    }
    return a;
}

Typical workflows involve initializing empty trees for each vertex, applying difference-array updates along paths, and executing a post-order traversal to merge child trees into parents.

Kruskal Reconstruction Trees

The Kruskal reconstruction tree transforms a weighted graph into a binary structure during Minimum Spanning Tree construction. Whenever an edge $(u, v)$ connects two disjoint components, a new internal node is created with a weight equal to the edge. The roots of the two components become children of this new node.

Core properties:

• The structure follows a monotonic weight distribution relative to depth.
• The lowest common ancestor of any two original vertices stores the minimum possible maximum edge weight on any path between them.
• Moving upward from a starting vertex $x$ to the shallowest ancestor with weight $\le W$ isolates all vertices reachable using only edges $\le W$. These vertices precisely match the leaves in that ancestor's subtree.

#include <algorithm>
#include <vector>

struct Edge { int u, v, w; };
const int MAX_V = 200010, LOG = 20;

int dsu_root[MAX_V], ancestor[MAX_V][LOG], edge_val[MAX_V], subtree_cnt[MAX_V];
int node_count;
std::vector<int> adj[MAX_V];

int find_set(int v) {
    return dsu_root[v] == v ? v : dsu_root[v] = find_set(dsu_root[v]);
}

void build_kruskal_tree(int n, std::vector<Edge>& edges) {
    std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.w < b.w;
    });
    node_count = n;
    for (int i = 0; i <= 2 * n; ++i) {
        dsu_root[i] = i;
        edge_val[i] = (i <= n) ? 0 : 0x3f3f3f3f;
    }

    for (auto& e : edges) {
        int ru = find_set(e.u), rv = find_set(e.v);
        if (ru == rv) continue;
        ++node_count;
        dsu_root[ru] = dsu_root[rv] = node_count;
        edge_val[node_count] = e.w;
        adj[node_count].push_back(ru);
        adj[node_count].push_back(rv);
    }
}

void dfs_lift(int u, int p) {
    subtree_cnt[u] = (adj[u].empty()) ? 1 : 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        ancestor[v][0] = u;
        for (int j = 1; j < LOG; ++j)
            ancestor[v][j] = ancestor[ancestor[v][j-1]][j-1];
        dfs_lift(v, u);
        subtree_cnt[u] += subtree_cnt[v];
    }
}

int query_constrained(int start, int limit) {
    int cur = start;
    for (int j = LOG - 1; j >= 0; --j) {
        int up = ancestor[cur][j];
        if (up && edge_val[up] <= limit) cur = up;
    }
    return cur;
}

After identifying the target ancestor via binary lifting, range queries over its DFS traversal interval solve order-statistic problems using persistent structures or merge-sort trees.

Sequence Maintenance with Splay Trees

Splay trees naturally model ordered sequences by treating in-order traversal as the array layout. Index-based menipulations become subtree operations. To target range $[L, R]$, the node at index $L-1$ is splayed to the root, and the node at $R+1$ is splayed to the root's right child. The target segment then resides entirely in the left subtree of the right child.

Lazy propagation efficiently handles range reversals. When a reversal flag is pushed down, child pointers are swapped and the flag is toggled for descendants. This structural symmetry makes Splay trees suitable for dynamic sequence problems like maximum subarray sum queries. Each node maintains four aggregate metrics: total sum, maximum prefix sum, maximum suffix sum, and maximum contiguous subarray sum. These values are recalculated during rotations and pushdown operations to reflect the current tree configuraton.

#include <algorithm>

const int MAX_SZ = 200015;
struct SplaySeq {
    int ch[MAX_SZ][2], par[MAX_SZ], sz[MAX_SZ];
    int val[MAX_SZ], rev_tag[MAX_SZ];
    int pref[MAX_SZ], suff[MAX_SZ], max_cont[MAX_SZ], sum[MAX_SZ];
    int root, ptr;

    void pull(int u) {
        int l = ch[u][0], r = ch[u][1];
        sz[u] = sz[l] + sz[r] + 1;
        sum[u] = sum[l] + sum[r] + val[u];
        pref[u] = std::max(pref[l], sum[l] + val[u] + std::max(0, pref[r]));
        suff[u] = std::max(suff[r], sum[r] + val[u] + std::max(0, suff[l]));
        max_cont[u] = std::max({max_cont[l], max_cont[r],
            std::max(0, suff[l]) + val[u] + std::max(0, pref[r])});
    }

    void push(int u) {
        if (rev_tag[u]) {
            std::swap(ch[u][0], ch[u][1]);
            std::swap(pref[u], suff[u]);
            if (ch[u][0]) rev_tag[ch[u][0]] ^= 1;
            if (ch[u][1]) rev_tag[ch[u][1]] ^= 1;
            rev_tag[u] = 0;
        }
    }

    bool is_right(int u) { return u == ch[par[u]][1]; }

    void rotate(int u) {
        int p = par[u], g = par[p], d = is_right(u);
        if (g) ch[g][is_right(p)] = u;
        ch[p][d] = ch[u][d ^ 1]; par[ch[u][d ^ 1]] = p;
        ch[u][d ^ 1] = p; par[p] = u;
        par[u] = g;
        pull(p); pull(u);
    }

    void splay(int u, int target = 0) {
        while (par[u] != target) {
            int p = par[u];
            if (par[p] != target)
                is_right(u) == is_right(p) ? rotate(p) : rotate(u);
            rotate(u);
        }
        if (!target) root = u;
        pull(u);
    }

    int find_kth(int k) {
        int cur = root;
        while (cur) {
            push(cur);
            if (k <= sz[ch[cur][0]]) cur = ch[cur][0];
            else if (k == sz[ch[cur][0]] + 1) return cur;
            else { k -= sz[ch[cur][0]] + 1; cur = ch[cur][1]; }
        }
        return -1;
    }

    void reverse_segment(int l, int r) {
        int u = find_kth(l), v = find_kth(r + 2);
        splay(u); splay(v, u);
        rev_tag[ch[v][0]] ^= 1;
    }
};

The structure supports arbitrary range modifications while preserving $O(\log N)$ amortized complexity through careful rebalancing during rotations.