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!