Mergeable Exact Order Statistics Data Structure Given $n$ sets of integers $S_1, S_2, \cdots, S_n$, it is guaranteed that
$$
x &lt; 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 &lt; 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 &lt; 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.

You can see this question on Stack Overflow for several references results. They include a paper on CGAL (red-black), a reference to the OCaml standard library (AVL), as well as the red-black tree chapter of CLRS's Introduction to Algorithms.

When I was learning about this topic, I was happy to find that $merge$ is actually usually a simpler operation than $insert$ and $delete$.