Segment Tree Merging Fundamentals

Segment tree merging combines two segment trees into one. The core algorithm processes corresponding nodes:

• If either node is empty, return the other
• Otherwise, recursively merge left and right subtrees

Node* merge(Node* x, Node* y) {
    if (!x) return y;
    if (!y) return x;
    
    x->value += y->value;
    x->left = merge(x->left, y->left);
    x->right = merge(x->right, y->right);
    return x;
}

For leaf-level merging with update propagation:

Node* merge(Node* x, Node* y, int l, int r) {
    if (!x) return y;
    if (!y) return x;
    
    if (l == r) {
        x->count += y->count;
        return x;
    }
    
    int mid = (l + r) / 2;
    x->left = merge(x->left, y->left, l, mid);
    x->right = merge(x->right, y->right, mid + 1, r);
    update(x);
    return x;
}

This technique is commonly used with dynamically allocated segment trees, which create nodes only when needed, conserving memory.

Practical Applications

Rainfall Tracking Problem

Track item distribution across tree nodes using value-range segment trees with tree differencing. Merge child trees into parent during post-order traversal.

Key Implementation Detail: Store results immediately after merging since further merging may alter node information due to the empty node handling logic.

void solve(int node) {
    for (int child : children[node]) {
        solve(child);
        root[node] = merge(root[node], root[child], 1, max_value);
    }
    result[node] = get_max_value(root[node]);
}

Promotion Counting

Each node maintains a value-range segment tree. Bottom-up merging enables querying nodes with values greater than current node's value.

void process_tree(int current) {
    for (int child : children[current]) {
        process_tree(child);
        root[current] = merge(root[current], root[child]);
    }
    answer[current] = query_greater(root[current], value[current]);
}

Island Connectivity with k-th Largest Query

Union-find maintains connectivity while segment trees handle k-th largest queries:

• Connect operations merge corresponding segment trees
• Query operations traverse the tree based on subtree sizes

int find_kth(Node* node, int k) {
    if (node->left_size >= k) 
        return find_kth(node->left, k);
    else 
        return find_kth(node->right, k - node->left_size);
}

Magic Girl LJJ Operations

Complex operations including:

• Dynamic node creation
• Tree merging
• Value range modifications
• k-th element queries
• Size comparisons using logarithmic sums

Root Heap Optimization

DFS-based approach with segment tree merging for optimal selection. Compare results using multiset-based alternative for improved performance.

multiset<int> sets[N];
void combine_sets(int target, int source) {
    if (sets[target].size() < sets[source].size())
        swap(sets[target], sets[source]);
    sets[target].insert(sets[source].begin(), sets[source].end());
}

Network Fusion Analysis

Offline processing with DFS ordering enables efficient connectivity queries. Segment trees maintain subtree information for edge removal impact calculations.

long long calculate_impact(int u, int v) {
    int root = find(u);
    int subtree_size = query_size(root, dfs_start[v], dfs_end[v]);
    int total_size = get_total_size(root);
    return (long long)subtree_size * (total_size - subtree_size);
}