# Mergeable Exact Order Statistics Data Structure

Given $n$ sets of integers $S_1, S_2, \cdots, S_n$, it is guaranteed that $$x < y, \text{ for } \forall x \in S_i \text{ and } \forall y \in S_{i+1}$$ and let's denote this relationship as $S_i < S_{i+1}$. For each set, we want to build a data structure that supports the following two operations:

• $rank(x)$: Return the rank of $x$ in $S_i$, where $x \in S_i$;

• $merge(A, B)$: Let $A$ and $B$ be the structures built on two sets $S_i$ and $S_j$ with $S_i < S_j$. Merge $A$ and $B$.

One implementation is to use an order statistics tree (such as AVL tree, red-black tree), which is able to support $\mathcal{O}(\log n)$ rank operation, but fails(right?) to provide efficient (i.e., logarithmic or constant) merge operation. A linked-list implementation, however, has poor rank performance. A skip-list may be employed, but its worst time complexity is bad.

Can anyone provide a reference about such a structure or proved lower bounds for a structure that supports these two operations at the same time? Any idea is appreciated. Thanks!

Most balanced trees that have logarithmic-time insert and delete also have logarithmic time $merge$. This includes AVL trees, red-black trees, and B trees.
When I was learning about this topic, I was happy to find that $merge$ is actually usually a simpler operation than $insert$ and $delete$.
One option would be a Treap (or (Implicit) Cartesian tree), though it only guarantees $\mathcal{O}(\log n)$ expected time for both operations.
Alternatively, a Splay Tree would give you $\mathcal{O}(\log n)$ amortized time for both operations.