Core Concepts and Prerequisites

To effectively implement merging operations on range-based data structures, understanding dynamic node allocation and order statistic trees is essential. Standard segment trees often consume excessive memory when built fully; dynamic initialization allowss resources to be allocated only for visited ranges.

Problem Scenario: Component Ordering

Consider a graph containing $N$ nodes, where each node possesses a unique value representing its priority or weight. Nodes are initially isolated or connected via paths defined by edges. The objective involves handling two primary types of updates:

1. Linking two distinct components together.
2. Querying the $K$-th smallest value within the currently connected component of a specific node.

Since queries require order statistics across a dynamically changing set, maintaining a separate segment tree for each connected component is a viable approach. When two components merge via an edge operation, their respective segment trees must also be combined to maintain accurate global statistics for the new unified component.

The Merge Strategy

When combining two valid segment trees representing the same domain (e.g., value ranges from $1$ to $N$), we recursively traverse corresponding nodes. If both trees have nodes in a specific range, their information is aggregated. If one path terminates (is null), the other's structure is adopted directly to save time.

There are two common implementation patterns for this operation:

Pattern 1: Destructive Update (Memory Efficient)

This method modifies the existing structure in place, typically discarding the second tree. This is preferred when memory constraints are tight, as it prevents duplicate node creation.

Pattern 2: Copy-on-Write (Immutable Logic)

Here, a fresh node is created during the merge process, leaving the original trees intact. While safer for multi-threaded environments, it incurs higher memory overhead.

Implementation Example

The following C++ implementation demonstrates the destructive merging approach using indices for storage efficiency. It integrates Disjoint Set Union (DSU) to manage connectivity and a dynamic segment tree to handle value tracking.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int MAX_NODES = MAXN * 20;

struct Node {
    int left_child;
    int right_child;
    int count;
} pool[MAX_NODES];

int root_pool[MAXN]; // Stores the root index for each node/component
int parent_set[MAXN]; // DSU structure
int val_map[MAXN];     // Maps rank to ID
int total_nodes = 0;

// Find operation for DSU with path compression
int find_set(int v) {
    if (v == parent_set[v]) return v;
    return parent_set[v] = find_set(parent_set[v]);
}

// Initialize a new leaf node
int create_node() {
    total_nodes++;
    pool[total_nodes].count = 0;
    pool[total_nodes].left_child = 0;
    pool[total_nodes].right_child = 0;
    return total_nodes;
}

// Insert value into the segment tree (Dynamic Allocation)
int insert_tree(int prev_root, int l, int r, int val) {
    int current = create_node();
    if (prev_root != 0) {
        pool[current].left_child = pool[prev_root].left_child;
        pool[current].right_child = pool[prev_root].right_child;
        pool[current].count = pool[prev_root].count;
    }
    
    pool[current].count++;
    if (l == r) return current;

    int mid = l + (r - l) / 2;
    if (val <= mid) {
        pool[current].left_child = insert_tree(pool[current].left_child, l, mid, val);
    } else {
        pool[current].right_child = insert_tree(pool[current].right_child, mid + 1, r, val);
    }
    return current;
}

// Merge two trees destructively into 'target'
// Returns the new root of the merged tree
int merge_trees(int target, int source, int l, int r) {
    if (!target) return source; // If target is empty, take source
    if (!source) return target; // If source is empty, keep target

    if (l == r) {
        pool[target].count += pool[source].count;
        return target;
    }

    int mid = l + (r - l) / 2;
    pool[target].left_child = merge_trees(pool[target].left_child, pool[source].left_child, l, mid);
    pool[target].right_child = merge_trees(pool[target].right_child, pool[source].right_child, mid + 1, r);
    pool[target].count = pool[pool[target].left_child].count + pool[pool[target].right_child].count;
    return target;
}

// Find k-th smallest value
int query_kth(int idx, int l, int r, int k) {
    if (pool[idx].count < k) return -1;
    if (l == r) return val_map[l];

    int mid = l + (r - l) / 2;
    int left_count = pool[pool[idx].left_child].count;

    if (k <= left_count) {
        return query_kth(pool[idx].left_child, l, mid, k);
    } else {
        return query_kth(pool[idx].right_child, mid + 1, r, k - left_count);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 1; i <= n; ++i) {
        parent_set[i] = i;
        int p_val;
        cin >> p_val;
        val_map[p_val] = i;
        root_pool[i] = insert_tree(0, 1, n, p_val);
    }

    // Initial static connections
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        int root_u = find_set(u);
        int root_v = find_set(v);
        if (root_u != root_v) {
            parent_set[root_u] = root_v;
            root_pool[root_v] = merge_trees(root_pool[root_v], root_pool[root_u], 1, n);
        }
    }

    int q;
    cin >> q;
    while (q--) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        if (op == 'B') {
            int ru = find_set(x);
            int rv = find_set(y);
            if (ru != rv) {
                parent_set[ru] = rv;
                root_pool[rv] = merge_trees(root_pool[rv], root_pool[ru], 1, n);
            }
        } else {
            int comp_root = root_pool[find_set(x)];
            cout << query_kth(comp_root, 1, n, y) << "\n";
        }
    }
    return 0;
}

Advanced Application Cases

The merge logic extends beyond simple connectivity problems.

Interval Color Changes In scenarios requiring frequent color updates (e.g., painting segments), maintaining a segment tree per color allows efficient merging when colors change. This reduces complexity compared to rebuilding structures after every udpate.

Offline Graph Queries For questions involving path restrictions (e.g., reaching a node using only edges below a certain threshold), sorting queries allows processing edges incrementally. As edges are added, component trees merge, enabling real-time $K$-th height retrieval on the fly.

Inversion Minimization To minimize inversion counts in tree traversal sequences, merging subtrees provides visibility into cross-product interactions. By calculating inversions formed between left-right branches versus right-left branches during the merge step, optimal swap decisions can be derived locally.