# Array-like data structure with O(1) worst-case concatenate/join?

I am looking for a data structure $D$ which supports the following operations (preferably a (binary) tree-like structure):

• $D$ is indexed, i.e. there is a mapping from $\{1, \ldots, n\}$ to items in $D$, where $n$ is the size of $D$ (the number of items in $D$).

• $k$-th item in $D$ can be accessed in $\mathcal{O}(\lg n)$ worst-case (non-amortized).
The operation should not modify the data structure, it should be completely "read-only" (e.g. no finger searches are allowed). (Once the pointer to the $k$-th item is obtained, further changes should be supported in $O(1)$ without modification to the state of the data structure apart from the actual stored item (e.g. if it is a tree-like data structure, this means no rotation is allowed).

• two instanced $D$ and $D'$ can be merged in time $\mathcal{O}(1)$ worst-case (non-amortized). Destruction of $D$ and $D'$ is fine.
The result should contains the union of the elements; those that come $D$ retain their indices, while indices of those coming from $D'$ get incremented by the size of $D$, e.g. if we are merging $D=\{ 1 \to x_1, 2 \to x_2 \}$ with $D'=\{ 1 \to y_1, 2 \to y_2, 3 \to y_3 \}$ we should get $\{ 1 \to x_1, 2 \to x_2, 3 \to y_1, 4 \to y_2, 5 \to y_3 \}$.

In essence, this data structure should have the properties of the fast-mergeable array/vector with asymptotically slower random-access, but extremely fast merge/concatenation ($\mathcal{O}(1)$). It would also be cool if elements could be listed in order in linear time.

I would be mostly interested in the references to existing work / papers which describe such a data structure or algorithm on an existing data structure.

• By sorted, I mean not by element values but by their index, which is let's say the order in which they were appended to the initially empty list-like data structure.
– eold
Jan 23, 2015 at 5:02
• Then you can just keep a separate list of items. Btw, I think the correct term for what you want is "indexed" not "sorted" or "ordered". Jan 23, 2015 at 5:23

• This feels strange, why merge is $O(1)$ but insert is $O(\lg n)$? Surely you can create a single item instance and merge, right? Jan 23, 2015 at 4:55
• @Kaveh, this data structure doesn't support $O(1)$ merge of interleaved keys, like the merge in the merge step of a mergesort. It supports constant-time concat (aka join), in which all of the slots in one structure end up following all of the slots of the other. This matches, IIUC, what the OP is asking about. Jan 23, 2015 at 5:00
• @leden: To use these trees, I think you don't actually need to store the indices at the elements. Instead, store at each internal node the number of descendant leaves. Starting from the root, to get to index $i$, if the left child has $j < i$ descendants, look fo index $i-j$ in the right subtree. Otherwise, look for index $i$ in the left subtree. This may not work exactly as written, but this reference is the closest thing I know of to what you request, so I think a modification of my suggestion may be the closest the literature has to an answer to your question. Jan 23, 2015 at 15:22