Small-to-Large Merging and the DSU on Tree Technique

Union by size is usually presented as a way to keep a parent-pointer forest shallow. The same accounting argument — always move the smaller side — does something different and more general: it bounds the total number of element moves in any sequence of merges of containers, whatever those containers hold. That generalization is the reason “merge the small into the large” appears far outside disjoint sets, in symbol table construction, in set-union implementations, and in the subtree-query technique that competitive programming calls DSU on tree.

The move-counting argument

Suppose each element carries a container identity, and a merge moves every element of the smaller container into the larger one. Consider one element’s history. Each time it moves, the container it lands in has at least twice the membership of the container it left, because it moved from the smaller side into the larger side, and the larger side was at least as big. Its container size therefore at least doubles at each move. Starting from 1 and ending at n, it can double at most ⌊log₂ n⌋ times. Total moves over all elements is at most n log₂ n.

The argument requires only that the size of each container be known, and that the merge move the smaller side. It does not require the containers to be sets, does not require any particular internal representation, and does not depend on the merge order. It also does not require the merge to be destructive in the union-find sense: the moved elements keep their identities and their payloads.

That last point is what distinguishes this from path compression. A compressed find rewrites links but moves nothing; small-to-large moves payloads but rewrites no links. The two techniques compose, and a structure that does both — a parent array for connectivity plus per-block member lists spliced small-into-large — pays O(n log n) for the splicing and O(m α(n)) for the queries.

#include <stdlib.h>
#include <string.h>

struct block {
    int   *members;
    size_t count, cap;
};

/* Move every member of `small` into `big`; caller has compared counts. */
static void absorb(struct block *big, struct block *small) {
    if (big->count + small->count > big->cap) {
        size_t cap = big->cap ? big->cap : 1;
        while (cap < big->count + small->count) cap *= 2;
        big->members = realloc(big->members, cap * sizeof *big->members);
        big->cap = cap;
    }
    memcpy(big->members + big->count, small->members,
           small->count * sizeof *small->members);
    big->count += small->count;
    free(small->members);
    small->members = NULL;      /* the block object itself is reused as a handle */
    small->count = small->cap = 0;
}

The copy loop is the expensive part: memcpy of small->count elements. Writing it as a per-element loop that also updates a per-element owner field is the same cost plus one store per element, which is what a member list that supports which block am I in requires.

The same trick without copying: linked lists

Copying is avoidable when the container only needs to be enumerable, not indexable. A singly linked list per block with head and tail pointers supports a splice in O(1): point the tail of the larger list at the head of the smaller one, and update the tail. No element moves, so the n log n bound collapses to O(1) per merge.

The trade is that the list must be walked to enumerate, and the walk order is no longer the merge order. It also means the “small into large” comparison is only needed for the size bookkeeping, not for the cost — but the size is still needed if the structure must report block sizes without walking.

A doubly linked list adds the ability to remove an element in O(1) given its node, which makes the structure support deletion from a block. That is the representation used when disjoint sets must also support “move this element to a new block”, a variant known as union-find with moves, where the moved element gets a fresh index rather than being unlinked in place.

Reusing one structure across a tree

The DSU-on-tree technique applies small-to-large in a different dimension: it merges the data of a node’s children into the node’s own structure, and answers a query about the subtree at that node. The naive approach builds a fresh structure per subtree, which costs O(n) per node and O(n²) overall on a path-shaped tree. The small-to-large approach keeps one structure per node, merges children into the largest child’s structure, and reuses that structure as the node’s own.

The algorithm, in outline:

1. Process the tree bottom-up, or recursively with the heavy child processed last.
2. For each node, start from the largest child’s accumulated structure.
3. Merge every other child’s structure into it, element by element.
4. Insert the node’s own value.
5. Answer the query for this node against the accumulated structure.

Each element is inserted once and moved at most log₂ n times, because the structure it lives in at least doubles each time it is merged into a larger one. The total work is O(n log n) insertions, plus the cost of the query at each node.

The technique is worth understanding for its constraint, not just its bound: the query must be answerable from a structure that accumulates a subtree’s contents and supports insertion of one element. It cannot answer queries that need to remove elements, because the structure is shared upward. A query such as “how many distinct colors in this subtree” fits, because insertion is the only mutation. A query such as “the maximum value on the path from this node to the root” does not, because it is not a subtree aggregate at all.

/* Children of u are reached via first_child[u] / next_sibling[].
   heavy[u] is the child with the largest subtree, or -1. */
static void dfs(int u, int keep) {
    for (int v = first_child[u]; v != -1; v = next_sibling[v])
        if (v != heavy[u])
            dfs(v, 0);                 /* light child: its counts are discarded */

    if (heavy[u] != -1)
        dfs(heavy[u], 1);              /* heavy child's counts are inherited as ours */

    for (int v = first_child[u]; v != -1; v = next_sibling[v])
        if (v != heavy[u])
            add_subtree(v);            /* re-insert each light subtree element */

    add(u);                            /* the structure now holds exactly subtree(u) */
    answer[u] = distinct;

    if (!keep)
        remove_subtree(u);             /* caller will re-insert these elements */
}

add_subtree is a plain traversal that calls add on every element of the subtree, and remove_subtree walks the same nodes decrementing the histogram. The pair is what makes the keep flag meaningful: without the removal, the structure would still hold a light child’s contents when the parent starts merging, and the counts would double.

The keep flag is the mechanism that makes the bound hold: a light child’s structure is thrown away after its own query, so its elements are re-inserted into the parent’s structure, and each such re-insertion corresponds to a doubling. The heavy child’s structure is kept and inherited, so its elements are never re-inserted at this level.

When the log factor is the wrong target

The n log n bound assumes the merge cost is proportional to the number of elements moved. When the merge itself is more expensive — merging two ordered containers, for instance — the accounting changes. Merging two balanced search trees by inserting the smaller one’s elements into the larger costs O(k log n) for k moved elements, which gives O(n log² n) over a balanced merge tree rather than the O(n log n) that the move count alone suggests.

Two alternatives exist for ordered containers. Merging two sorted arrays costs O(a + b) but produces a new array, so the total over a balanced merge tree is O(n log n) moves regardless of which side is smaller — the small-to-large rule buys nothing, because every element is rewritten at every level. Destructive merging that reuses the larger array’s storage changes the constant, not the bound, unless one side is empty. The small-to-large rule still helps when the containers are trees and merging them can be done without visiting every element of the larger one; that is the case where the rule is a real optimization rather than a bookkeeping habit.

The practical lesson is that small-to-large is a bound on element moves, and its value depends on the move being cheap. When the move requires a search, the cost model changes and the accounting must be redone.

Failure modes

Sizes must be exact and current. A stale size makes the “smaller” side wrong, which does not break correctness but destroys the bound. In a structure where sizes are recomputed lazily, the recomputation must happen before the comparison.

Merging by size is not merging by cost. If one container is cheap to merge and the other is expensive, size is a proxy for cost that can be badly wrong. A block with a huge auxiliary index and few members may be expensive to absorb despite being smaller.

Recursion depth. The bottom-up formulation over a path-shaped tree recurses n levels deep. The keep-flag formulation above recurses to the height of the tree, which is n for a path, so the implementation must either be iterative or run on a thread with a large stack.

The log is base two. Each merge doubles, so the bound is log₂ n moves per element, not log₁₀ n. For n = 10⁶ that is 20 moves per element, 20 million moves total. That is the number to compare against a per-element cost when deciding whether the technique is affordable.

Where the merge must also be undoable, the small-to-large bookkeeping becomes part of the rollback log, which is the subject of Rollback Union-Find and Offline Dynamic Connectivity. Where the merged structure is a bitmap, the merge is a word-wise OR and the bound is replaced by a factor of w, as described in Bitset Representation and Word-Level Rank and Select.