---
title: "Small-to-Large Merging"
summary: Why merging the smaller container into the larger one gives O(n log n) total work, and the dozen problems where that one line is the whole solution.
difficulty: hard
tags: [trees, maps, amortised]
time: n log n or n log^2 n
space: n
prereq: [trees/dfs, complexity/classes]
see: [advanced-tree/centroid, structures/dsu]
---

:::definition label="The rule"
When combining the data of several children into their parent, always iterate over the **smaller** structure and insert into the **largest** one (then rename/merge pointers), never the reverse.
:::

:::theorem title="Each element moves O(log n) times"
In a DFS that merges children's sets into the parent's, each vertex (element) is re-inserted at most $\log_2 n$ times, so the total number of insertions is $O(n \log n)$, and $O(n \log^2 n)$ with `std::set`/`map` (log per insertion) or $O(n\log n)$ with `unordered_map`.
:::

:::proof
When an element is moved, it goes from a container of size $a$ into one of size $b \ge a$, so the container holding it at least doubles. Its size can double at most $\log_2 n$ times before reaching $n$. Multiply by the cost of one insertion. ∎
:::

```cpp small-to-large.cpp
// "for every vertex v: how many distinct colours appear in v's subtree?"
vector<unordered_map<int,int>*> cnt(n);        // colour -> occurrences
vector<int> ans(n);
int dfs(int v, int p) {
    auto best = new unordered_map<int,int>();  int bestsz = 0, idbest = -1;
    for (int to : g[v]) if (to != p) {
        int sz = dfs(to, v);
        if (sz > bestsz) { bestsz = sz; idbest = to; }
    }
    if (idbest != -1) { delete best; best = cnt[idbest]; }   // steal the big one
    (*best)[colour[v]]++;
    for (int to : g[v]) if (to != p && to != idbest) {
        for (auto &[c, k] : *cnt[to]) (*best)[c] += k;       // small into large
        delete cnt[to]; cnt[to] = nullptr;
    }
    cnt[v] = best; ans[v] = best->size();
    return best->size();
}
```

:::props title="What the trick solves"
- distinct colours / values per subtree (the above),
- "the most frequent colour in each subtree" (CF 600E *Lomsat gelral*, the canonical statement),
- subtree set intersection queries: "does subtree $u$ contain a vertex of colour $c$?" → answer with maps built once, $O(1)$ per query after $O(n\log n)$,
- merging tries: each node's subtree trie built by insertion-merge ⇒ $O(n \log n \cdot L)$ for "maximum xor of two values in the same subtree",
- DSU-on-tree (@advanced-tree/small-to-large) is the *memory-light* variant: keep one global array, add/remove subtrees, and exploit the same "light subtrees are touched $\log$ times" count,
- polynomial/convolution merging on trees ("count pairs at distance $d$ in each subtree"): merging small-to-large turns an $O(n^2)$ DP into $O(n \log^2 n)$.
:::

:::note title="Small-to-large vs. DSU on tree vs. centroid"
| | memory | supports | cost |
|---|---|---|---|
| merge containers (here) | $O(n)$ structures, but allocation-heavy | per-vertex *answers for all subtrees* | $n\log n$ inserts, simple |
| DSU on tree (sack) | one global array | per-vertex answers, with add/remove semantics; easy to also handle "path to root" | same count, but only $O(n)$ memory and cache-friendly |
| centroid decomposition (@advanced-tree/centroid) | $O(n \log n)$ | **pairs across the whole tree** with a distance constraint, or global queries | $n\log n$ with different bookkeeping |
:::

:::warning title="Three ways to lose the log"
1. Merging by `map::merge`/insert loop **without** first picking the largest child as the base — then the big map is the destination only by accident; the bound is $O(n^2)$ on a path.
2. Copying instead of moving: `auto m = *child;` silently doubles the work; keep pointers (or `std::move`) and always leave the biggest child's container in place.
3. Forgetting that `std::map::merge` is $O(\text{size} \cdot \log)$ *per element*, so total is $n\log^2 n$ — fine at $n \le 2\times10^5$ ($\approx 6\times10^7$), fatal at $10^6$. `unordered_map` + reserve wins by 3–4×; a global array + DSU-on-tree wins by 10×.
:::

:::problems
- [[CF 600E]] Lomsat gelral | https://codeforces.com/problemset/problem/600/E | core | the standard small-to-large statement
- [[CSES 1137]] Subtree Queries | https://cses.fi/problemset/task/1137 | easy | the flattening alternative — compare the two approaches on the same data
:::