# Small-To-Large Merging

Authors: Michael Cao, Benjamin Qi

A way to merge two sets efficiently.

## Merging Data Structures

Obviously linked lists can be merged in $O(1)$ time. But what about sets or vectors?

Focus Problem – read through this problem before continuing!

Let's consider a tree rooted at node $1$, where each node has a color.

For each node, let's store a set containing only that node, and we want to merge the sets in the nodes subtree together such that each node has a set consisting of all colors in the nodes subtree. Doing this allows us to solve a variety of problems, such as query the number of distinct colors in each subtree.

### Naive Solution

Suppose that we want merge two sets $a$ and $b$ of sizes $n$ and $m$, respectively. One possiblility is the following:

for (int x: b) a.insert(x);

which runs in $O(mg(n+m))$ time, yielding a runtime of $O(N_{2}gN)$ in the worst case. If we instead maintain $a$ and $b$ as sorted vectors, we can merge them in $O(n+m)$ time, but $O(N_{2})$ is also too slow.

### Better Solution

With just one additional line of code, we can significantly speed this up.

if (a.size() < b.size()) swap(a,b);for (int x: b) a.insert(x);

Note that swap exchanges two sets in $O(1)$ time. Thus, merging a smaller set of size $m$ into the larger one of size $n$ takes $O(mgn)$ time.

**Claim:** The solution runs in $O(Ng_{2}N)$ time.

**Proof:** When merging two sets, you move from the smaller set to the larger set. If the size of the smaller set is $X$, then the size of the resulting set is at least $2X$. Thus, an element that has been moved $Y$ times will be in a set of size at least $2_{Y}$, and since the maximum size of a set is $N$ (the root), each element will be moved at most $O(gN$) times.

Full Code

## Generalizing

We can also merge other standard library data structures such as `std::map`

or `std:unordered_map`

in the same way. However, `std::swap`

does not always run in $O(1)$ time. For example, swapping `std::array`

s takes time linear in the sum of the sizes of the arrays, and the same goes for GCC policy-based data structures such as `__gnu_pbds::tree`

or `__gnu_pbds::gp_hash_table`

.

To swap two policy-based data structures `a`

and `b`

in $O(1)$ time, use `a.swap(b)`

instead. Note that for standard library data structures, `swap(a,b)`

is equivalent to `a.swap(b)`

.

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

CF | Normal | ## Show TagsMerging | Check CF | |||

Plat | Normal | ## Show TagsMerging, Indexed Set | ||||

Plat | Normal | ## Show TagsMerging | External Sol | |||

POI | Normal | ## Show TagsMerging, Indexed Set | External Sol | |||

IOI | Normal | ## Show TagsCentroid, Merging | External Sol | |||

JOI | Hard | ## Show TagsMerging |

It's easy to merge two sets of sizes $n≥m$ in $O(n+m)$ or $(mgn)$ time, but sometimes $O(mg(1+mn ))$ can be significantly better than both of these. Check "Advanced - Treaps" for more details. Also see this link regarding merging segment trees.

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

## Give Us Feedback on Small-To-Large Merging!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.