Authors: Michael Cao, Benjamin Qi
A way to merge two sets efficiently.
Obviously linked lists can be merged in time. But what about sets or vectors?
Focus Problem – read through this problem before continuing!
Let's consider a tree rooted at node , 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.
Suppose that we want merge two sets and of sizes and , respectively. One possiblility is the following:
for (int x: b) a.insert(x);
which runs in time, yielding a runtime of in the worst case. If we instead maintain and as sorted vectors, we can merge them in time, but is also too slow.
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 time. Thus, merging a smaller set of size into the larger one of size takes time.
Claim: The solution runs in time.
Proof: When merging two sets, you move from the smaller set to the larger set. If the size of the smaller set is , then the size of the resulting set is at least . Thus, an element that has been moved times will be in a set of size at least , and since the maximum size of a set is (the root), each element will be moved at most ) times.
We can also merge other standard library data structures such as
std:unordered_map in the same way. However,
std::swap does not always run in time. For example, swapping
std::arrays takes time linear in the sum of the sizes of the arrays, and the same goes for GCC policy-based data structures such as
To swap two policy-based data structures
b in time, use
a.swap(b) instead. Note that for standard library data structures,
swap(a,b) is equivalent to
Merging, Indexed Set
Merging, Indexed Set
It's easy to merge two sets of sizes in or time, but sometimes can be significantly better than both of these. Check "Advanced - Treaps" for more details. Also see this link regarding merging segment trees.
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.