⚙️AlgorithmIntermediate

Small-to-Large Principle

Key Points

•
Small-to-large means always merge the smaller container into the larger one to keep total work low.
•
Each element can move only O(log n) times because every time it moves, the container it joins at least doubles in size.
•
This turns many seemingly quadratic merging routines into O(n log n) total time over all merges.
•
It is the core idea behind DSU-on-tree (aka sack technique) and efficient merging of sets, maps, and lists.
•
In hash-based containers the total expected time becomes O(n log n), while in balanced BST maps it is O(n lo $g^{2}$ n).
•
Implementation pattern: if size(A) < size(B) then swap(A, B); then insert every element of A into B; clear A.
•
Use amortized analysis or a doubling argument to justify the O(log n) move bound per element.
•
Beware rehashing costs and iterator invalidation; always merge into the currently largest container.

Prerequisites

→Asymptotic notation — To interpret O(n), O(n log n), and compare algorithm growth rates.
→Hash tables and balanced BSTs — To understand per-insert costs and how they affect total complexity.
→Amortized analysis — To grasp why elements moving O(log n) times leads to O(n log n) total work.
→Tree traversal (DFS) — Needed for DSU-on-tree implementations that merge children into parents.
→Reference and move semantics in C++ — To implement efficient merges without unnecessary copying.
→Priority queues and k-way merge (optional) — To compare small-to-large with heap-based alternatives for merging sorted lists.

Detailed Explanation

Tap terms for definitions

01Overview

The small-to-large principle is a simple but powerful strategy for merging collections efficiently. The rule is: when combining two containers (like sets, maps, counters, or sorted lists), always insert elements from the smaller container into the larger one. Why does this matter? Because it ensures that each element doesn’t migrate too many times. Every time an element moves, it joins a container at least as big as its previous one, so the container it belongs to roughly doubles in size after a few moves. After at most about log n such doublings (where n is the total number of elements across all containers), an element reaches the largest container and stops moving. This amortized "at most log n moves per element" bound transforms many naive O(n^2) procedures into O(n log n) totals.

This principle underlies DSU-on-tree (also called the sack technique), where each tree node maintains a bag of information from its subtree, and children’s bags are merged into the parent by always merging smaller into larger. It also appears in repeated merging of sets/maps, multiway merging of sorted lists, and even in certain persistent segment tree merging patterns. Practically, you’ll implement it by checking sizes before merging and swapping references so the destination is the larger container. The approach is easy to code, cache-friendly when applied well, and widely applicable in competitive programming and systems that accumulate data incrementally.

02Intuition & Analogies

Imagine you and your friends are combining sticker collections. If every time two people combine, the person with fewer stickers puts theirs into the person with more, then each sticker moves to a bigger and bigger album. A sticker might move from a 3-sticker album to a 7-sticker one, then to a 15-sticker one, and so on. It doesn’t keep bouncing around endlessly—after a handful of moves, it ends up in a huge album and stays there.

This “move to a bigger home” story is exactly the small-to-large idea. The key is that your sticker’s home size grows fast—roughly doubling after some number of moves. Since you can only double the size about log n times before reaching n (the total number of stickers), each sticker can’t get moved more than O(log n) times. If each move is cheap (e.g., hash map insertion), then the total cost across all stickers is just the number of stickers times log n.

Contrast this with a careless approach where someone always dumps their stickers into a random album, or into a smaller album—then the same sticker could get moved around many more times, potentially creating quadratic work. Small-to-large protects you from that by enforcing a monotone growth of container size around each element’s journey. It’s like always riding an elevator that only goes up: there’s a strict limit to how many floors you can pass before you’re at the top.

03Formal Definition

Suppose we maintain a family of disjoint containers

C_{1}

C_{2}

, ..., each holding elements from a universe U, with total elements n =

\sum_{i}

∣ C_{i} ∣

. We repeatedly perform merges of two containers A and B by inserting all elements of the smaller container into the larger container. Formally, if

∣ A ∣

\leq

∣ B ∣

, then for each x

\in

A we perform an insertion x into B, then discard A. If the per-element insertion cost is bounded by

Θ

(1) expected time (e.g., average-case hash table insertion) or by

Θ

(

lo g

m) worst-case time into a balanced BST of size m, then the total cost over any sequence of merges satisfies: - Hash-based case: each element is moved at most O(

lo g

n) times, so total time is O(n

lo g

n) in expectation. - Balanced BST case: each move costs O(

lo g

n) and there are O(

lo g

n) moves per element, giving O(n

lo g^{2}

n) worst-case. The core amortization uses the doubling lemma: whenever an element moves from a container of size s to another container under small-to-large, the destination has size at least s. Hence the container size associated with that element at least doubles after a bounded number of moves; after O(

lo g

n) doublings, it cannot grow further, thus bounding the total number of moves per element.

04When to Use

Use small-to-large whenever you must repeatedly combine many containers and the naive approach risks moving the same elements many times.

Common scenarios include:

DSU on tree (sack technique): For each tree node, you maintain a container summarizing its subtree (e.g., color counts or distinct values). Merge each child’s container into the parent, always moving the smaller into the larger.
Merging sets/maps: You have a collection of sets or maps and need their union or combined counts. Merging smaller into larger ensures that each element changes containers only O(\log n) times.
K-way merging of sorted lists by repeated pairwise merges: If you must do sequential pairwise merges (not using a heap), merging smaller into larger bounds total copies per element by O(\log n).
Segment tree merging or divide-and-conquer data accumulation: When nodes are combined into parents, merging smaller sub-results into larger ones keeps complexity near O(n \log n).

Choose this strategy when per-insert cost is cheap (hash maps/sets) or when extra log factors are acceptable (balanced BSTs). If a true O(n \log k) optimal k-way merge is needed for sorted sequences, a min-heap may be better; however, when the algorithm structure forces repeated container merges, small-to-large is the standard tool.

⚠️Common Mistakes

Forgetting to swap by size: If you don’t ensure you always merge smaller into larger, elements may bounce around too many times, returning you to near-quadratic performance.
Assuming O(n \log n) with ordered maps: With std::map (balanced BST), each insertion costs O(\log n), so the total becomes O(n \log^2 n) worst-case. Use unordered_map/set for expected O(n \log n) if acceptable.
Ignoring rehashing and load factors: With unordered_map/set, frequent rehashes can add overhead. Reserve capacity or allow the container to grow naturally; the amortized argument still holds, but constants improve with reserve.
Copying instead of moving: When merging vectors or strings, prefer moving or appending from the smaller into the larger rather than copying both ways. Avoid building new containers unnecessarily if you can reuse the larger one.
Iterator invalidation: Inserting into unordered containers can invalidate iterators from the smaller container if you merge in-place incorrectly. Iterate over a snapshot (e.g., range-for on a separate reference) or collect keys first.
Counting wrong complexity unit: The O(n \log n) bound counts element moves. If per-insert is not O(1) expected (e.g., custom expensive merge logic), multiply the O(\log n) move bound by that per-insert cost to get the right total.

Key Formulas

Move bound per element

k \leq ⌊ lo g_{2} \frac{n}{s _{0}} ⌋

Explanation: If an element starts in a container of size $s_{0}$ and each move goes into a container at least as large, after k moves its container size is at least $s_{0}$ 2^k. This cannot exceed n, so k is at most floor(log base 2 of n/ $s_{0}$ ).

Total move count

x = 1 \sum n O (lo g n) = O (n lo g n)

Explanation: Summing the O(log n) move bound over all n elements gives O(n log n) total element moves. This is the core amortized complexity for small-to-large merging with O(1) per move.

General time with per-insert cost

T (n) = O (n lo g n) \cdot c_{ins}

Explanation: If each insertion has cost $c_{i} n s$ (e.g., expected O(1) for hash insertion), the total time is O(n log n) times that cost. For hash containers, $c_{i} n s$ is constant on average.

Ordered map case

T (n) = O (n lo g n) \cdot O (lo g n) = O (n lo g^{2} n)

Explanation: With balanced BST maps/sets, each insert costs O(log n) worst-case. Since each element moves O(log n) times, the total becomes O(n lo $g^{2}$ n).

Edge-based merge bound

i = 1 \sum m min {∣ A_{i} ∣, ∣ B_{i} ∣} \leq n lo g_{2} n

Explanation: Across any sequence of merges, charging the cost to the smaller set yields a bound of at most n log n. Each element can be charged only O(log n) times as the set it belongs to at least doubles between charges.

Potential function

Φ = j \sum ∣ C_{j} ∣ lo g ∣ C_{j} ∣

Explanation: This potential increases by at most O( $min$ \{ $∣ A ∣$ , $∣ B ∣$ \} $lo g$ n) when merging A and B. Summing over merges bounds the total work by O(n log n) up to constants, giving an amortized argument.

Complexity Analysis

Let n be the total number of elements across all containers prior to merging. Under small-to-large, any time an element moves, it goes from a container of size s to one of size at least s, so after a bounded number of moves, the container holding that element has size at least doubled. Therefore each element moves at most O(log n) times. If the per-insert operation is expected O(1) (e.g., std::unordere

d_{m} a p

/set with a good hash and typical load factor), the total expected time is O(n log n). If the per-insert is O(log n) worst-case (e.g., std::map/std::set), the total worst-case time becomes O(n lo

g^{2}

n). Space usage is O(n): we store each element once, and temporary overhead is proportional to container management; after merging, we typically clear the smaller container. For merging sorted vectors by rewriting into the larger container, each merge costs O(

∣ A ∣

∣ B ∣

). Although this seems to copy the large vector repeatedly, an element can be part of at most O(log n) such large rewrites because the size of the vector containing it at least doubles between rewrites. Thus the total copying across all merges remains O(n log n). In contrast, without small-to-large (e.g., always merging into a smaller container or picking merges adversarially), the same elements may be copied O(n) times, leading to near-quadratic behavior. Constants depend on hashing quality, rehash frequency, and memory locality; reserving capacity in hash containers and minimizing allocations for vectors can improve practical performance.

Code Examples

Merging many frequency maps (small-to-large with unordered_map)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Merge map 'small' into map 'large'. After the call, 'large' contains all counts,
5 // and 'small' is cleared. Always ensure small.size() <= large.size() when calling.
6 void merge_maps(unordered_map<int,int>& large, unordered_map<int,int>& small) {
7     // Move every (key, count) from small into large
8     for (const auto& kv : small) {
9         large[kv.first] += kv.second; // average O(1)
10     }
11     small.clear();
12 }
13 
14 int main() {
15     ios::sync_with_stdio(false);
16     cin.tie(nullptr);
17 
18     // Example: merge K maps of integer frequencies into one map
19     int K = 4;
20     vector<unordered_map<int,int>> maps(K);
21 
22     // Fill some sample data
23     maps[0] = {{1,2}, {3,1}};                 // {1:2, 3:1}
24     maps[1] = {{2,4}, {3,3}, {5,1}};          // {2:4, 3:3, 5:1}
25     maps[2] = {{1,1}, {4,5}};                 // {1:1, 4:5}
26     maps[3] = {{2,2}, {6,7}, {7,1}, {8,1}};   // {2:2, 6:7, 7:1, 8:1}
27 
28     // Repeatedly merge maps using small-to-large
29     // We will accumulate everything into index 'big'
30     int big = 0;
31     for (int i = 1; i < K; ++i) {
32         // Ensure we always merge smaller into larger
33         if (maps[i].size() > maps[big].size()) swap(maps[i], maps[big]);
34         merge_maps(maps[big], maps[i]);
35     }
36 
37     // Print result
38     for (auto &kv : maps[big]) {
39         cout << kv.first << ": " << kv.second << "\n";
40     }
41 
42     return 0;
43 }
44

We maintain K frequency maps and merge them into one by always merging the smaller map into the larger map. Each key’s count is moved only when its current map is the smaller partner. Because the container it joins is at least as large as the one it leaves, each key moves O(log n) times overall. With unordered_map insertions being average O(1), the total expected time is O(n log n), where n is the total number of key entries across all maps.

Time: Expected O(n log n) over all mergesSpace: O(n)

DSU on tree (sack): number of distinct colors in each subtree

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Small-to-large DSU-on-tree: For each node u, compute the number of distinct colors in its subtree.
5 // We merge each child's map into the largest child's map, then add u's color.
6 
7 const int MAXN = 200000;
8 vector<int> g[MAXN];
9 int colorArr[MAXN];
10 int n;
11 
12 // For each node, we maintain a map from color -> frequency inside its subtree
13 vector<unordered_map<int,int>> bag; // bag[u]
14 vector<int> ans;
15 
16 void dfs(int u, int p) {
17     int heavy = -1; // child with largest bag
18     // First process all children
19     for (int v : g[u]) if (v != p) {
20         dfs(v, u);
21         if (heavy == -1 || bag[v].size() > bag[heavy].size()) heavy = v;
22     }
23 
24     if (heavy == -1) {
25         // Leaf: start with its own color
26         bag[u][colorArr[u]] = 1;
27         ans[u] = (int)bag[u].size();
28         return;
29     }
30 
31     // Swap u's bag with heavy child's bag so u uses the largest bag
32     swap(bag[u], bag[heavy]);
33 
34     // Merge all other children (smaller) into u (larger)
35     for (int v : g[u]) if (v != p && v != heavy) {
36         // Ensure bag[v] is the smaller one by construction
37         for (const auto &kv : bag[v]) {
38             bag[u][kv.first] += kv.second; // average O(1)
39         }
40         bag[v].clear();
41     }
42 
43     // Add u's own color
44     bag[u][colorArr[u]]++;
45 
46     // The number of distinct colors equals the number of keys present
47     ans[u] = (int)bag[u].size();
48 }
49 
50 int main() {
51     ios::sync_with_stdio(false);
52     cin.tie(nullptr);
53 
54     // Input format:
55     // n
56     // colors[1..n]
57     // n-1 edges (u v)
58     if (!(cin >> n)) return 0;
59     for (int i = 1; i <= n; ++i) cin >> colorArr[i];
60     for (int i = 0; i < n-1; ++i) {
61         int u, v; cin >> u >> v;
62         g[u].push_back(v);
63         g[v].push_back(u);
64     }
65 
66     bag.assign(n + 1, unordered_map<int,int>());
67     ans.assign(n + 1, 0);
68 
69     dfs(1, 0);
70 
71     for (int i = 1; i <= n; ++i) {
72         cout << ans[i] << (i == n ? '\n' : ' ');
73     }
74     return 0;
75 }
76

For each node u, we maintain a hash map of color frequencies within its subtree. We identify the heavy child (largest map) and swap it into u. Then we merge every other child’s smaller map into u’s larger map. Finally we insert u’s color. Because we always merge smaller into larger, each color entry across the whole tree moves O(log n) times in expectation; hence the total expected time is O(n log n). The answer for u is simply the number of distinct colors (keys) in bag[u].

Time: Expected O(n log n)Space: O(n)

Pairwise merging of many sorted vectors using small-to-large

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Merge two sorted vectors 'small' into 'large' and store result back into 'large'.
5 // Always ensure small.size() <= large.size().
6 void merge_into(vector<int>& large, vector<int>& small) {
7     vector<int> out;
8     out.reserve(large.size() + small.size());
9     size_t i = 0, j = 0;
10     while (i < large.size() && j < small.size()) {
11         if (large[i] <= small[j]) out.push_back(large[i++]);
12         else out.push_back(small[j++]);
13     }
14     while (i < large.size()) out.push_back(large[i++]);
15     while (j < small.size()) out.push_back(small[j++]);
16     large.swap(out); // large becomes the merged result
17     small.clear();
18 }
19 
20 int main() {
21     ios::sync_with_stdio(false);
22     cin.tie(nullptr);
23 
24     // Example lists
25     vector<vector<int>> lists = {
26         {1, 5, 9},
27         {2, 3, 10, 11},
28         {4, 6},
29         {0, 7, 8, 12, 13}
30     };
31 
32     // Accumulate by always merging a smaller list into the biggest-so-far list
33     // We keep the result in index 'big'
34     int big = 0;
35     for (int i = 1; i < (int)lists.size(); ++i) {
36         if (lists[i].size() > lists[big].size()) swap(lists[i], lists[big]);
37         merge_into(lists[big], lists[i]);
38     }
39 
40     // Print merged sorted sequence
41     for (int x : lists[big]) cout << x << ' ';
42     cout << '\n';
43     return 0;
44 }
45

We merge multiple sorted vectors by repeatedly merging a smaller vector into the larger accumulated vector. Even though each merge copies the larger vector, any element participates in at most O(log n) such merges because the size of its container at least doubles between merges. Thus the total work over all merges is O(n log n), where n is the sum of lengths of all lists. If you can use a heap-based k-way merge, you get O(n log k); here we show the small-to-large approach for settings that require sequential merges.

Time: O(n log n) total over all mergesSpace: O(n) extra during each merge (temporary buffer)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Merge map 'small' into map 'large'. After the call, 'large' contains all counts,
5	// and 'small' is cleared. Always ensure small.size() <= large.size() when calling.
6	void merge_maps(unordered_map<int,int>& large, unordered_map<int,int>& small) {
7	// Move every (key, count) from small into large
8	for (const auto& kv : small) {
9	large[kv.first] += kv.second; // average O(1)
10	}
11	small.clear();
12	}
13
14	int main() {
15	ios::sync_with_stdio(false);
16	cin.tie(nullptr);
17
18	// Example: merge K maps of integer frequencies into one map
19	int K = 4;
20	vector<unordered_map<int,int>> maps(K);
21
22	// Fill some sample data
23	maps[0] = {{1,2}, {3,1}}; // {1:2, 3:1}
24	maps[1] = {{2,4}, {3,3}, {5,1}}; // {2:4, 3:3, 5:1}
25	maps[2] = {{1,1}, {4,5}}; // {1:1, 4:5}
26	maps[3] = {{2,2}, {6,7}, {7,1}, {8,1}}; // {2:2, 6:7, 7:1, 8:1}
27
28	// Repeatedly merge maps using small-to-large
29	// We will accumulate everything into index 'big'
30	int big = 0;
31	for (int i = 1; i < K; ++i) {
32	// Ensure we always merge smaller into larger
33	if (maps[i].size() > maps[big].size()) swap(maps[i], maps[big]);
34	merge_maps(maps[big], maps[i]);
35	}
36
37	// Print result
38	for (auto &kv : maps[big]) {
39	cout << kv.first << ": " << kv.second << "\n";
40	}
41
42	return 0;
43	}
44

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Small-to-large DSU-on-tree: For each node u, compute the number of distinct colors in its subtree.
5	// We merge each child's map into the largest child's map, then add u's color.
6
7	const int MAXN = 200000;
8	vector<int> g[MAXN];
9	int colorArr[MAXN];
10	int n;
11
12	// For each node, we maintain a map from color -> frequency inside its subtree
13	vector<unordered_map<int,int>> bag; // bag[u]
14	vector<int> ans;
15
16	void dfs(int u, int p) {
17	int heavy = -1; // child with largest bag
18	// First process all children
19	for (int v : g[u]) if (v != p) {
20	dfs(v, u);
21	if (heavy == -1 \|\| bag[v].size() > bag[heavy].size()) heavy = v;
22	}
23
24	if (heavy == -1) {
25	// Leaf: start with its own color
26	bag[u][colorArr[u]] = 1;
27	ans[u] = (int)bag[u].size();
28	return;
29	}
30
31	// Swap u's bag with heavy child's bag so u uses the largest bag
32	swap(bag[u], bag[heavy]);
33
34	// Merge all other children (smaller) into u (larger)
35	for (int v : g[u]) if (v != p && v != heavy) {
36	// Ensure bag[v] is the smaller one by construction
37	for (const auto &kv : bag[v]) {
38	bag[u][kv.first] += kv.second; // average O(1)
39	}
40	bag[v].clear();
41	}
42
43	// Add u's own color
44	bag[u][colorArr[u]]++;
45
46	// The number of distinct colors equals the number of keys present
47	ans[u] = (int)bag[u].size();
48	}
49
50	int main() {
51	ios::sync_with_stdio(false);
52	cin.tie(nullptr);
53
54	// Input format:
55	// n
56	// colors[1..n]
57	// n-1 edges (u v)
58	if (!(cin >> n)) return 0;
59	for (int i = 1; i <= n; ++i) cin >> colorArr[i];
60	for (int i = 0; i < n-1; ++i) {
61	int u, v; cin >> u >> v;
62	g[u].push_back(v);
63	g[v].push_back(u);
64	}
65
66	bag.assign(n + 1, unordered_map<int,int>());
67	ans.assign(n + 1, 0);
68
69	dfs(1, 0);
70
71	for (int i = 1; i <= n; ++i) {
72	cout << ans[i] << (i == n ? '\n' : ' ');
73	}
74	return 0;
75	}
76

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Merge two sorted vectors 'small' into 'large' and store result back into 'large'.
5	// Always ensure small.size() <= large.size().
6	void merge_into(vector<int>& large, vector<int>& small) {
7	vector<int> out;
8	out.reserve(large.size() + small.size());
9	size_t i = 0, j = 0;
10	while (i < large.size() && j < small.size()) {
11	if (large[i] <= small[j]) out.push_back(large[i++]);
12	else out.push_back(small[j++]);
13	}
14	while (i < large.size()) out.push_back(large[i++]);
15	while (j < small.size()) out.push_back(small[j++]);
16	large.swap(out); // large becomes the merged result
17	small.clear();
18	}
19
20	int main() {
21	ios::sync_with_stdio(false);
22	cin.tie(nullptr);
23
24	// Example lists
25	vector<vector<int>> lists = {
26	{1, 5, 9},
27	{2, 3, 10, 11},
28	{4, 6},
29	{0, 7, 8, 12, 13}
30	};
31
32	// Accumulate by always merging a smaller list into the biggest-so-far list
33	// We keep the result in index 'big'
34	int big = 0;
35	for (int i = 1; i < (int)lists.size(); ++i) {
36	if (lists[i].size() > lists[big].size()) swap(lists[i], lists[big]);
37	merge_into(lists[big], lists[i]);
38	}
39
40	// Print merged sorted sequence
41	for (int x : lists[big]) cout << x << ' ';
42	cout << '\n';
43	return 0;
44	}
45