Is there a data structure for representing sequences that supports the operations:concat takes two sequences of size $m$ and $n$ and produces a new sequence of size $m+n$ by joining them in time $o(\lg \min(n,m/n))$ (or $o(\lg \min(m,n/m))$ if $n>m$).For some constants $c$ and $N$, approximate split takes a sequence of size $n > N$ and divides it into two contiguous non-overlapping sequences of sizes $p$ and $q$ such that $p+q = n$ and $1/c < p/q < c$ in time $o(\lg n)$singleton takes a single element and produces a sequence containing only that element in $O(1)$ time.linearize takes a sequence of size $n$ and produces an array of size $n$ containing the elements of the sequence in time $O(n)$.I'm really looking for worst-case or expected bounds on the time, but amortized bounds would also be interesting. Results in the word RAM would be interesting as well.Here are some results I am aware of. In this table, sloppy split is like approximate split, but the bounds are $1/c < (\lg p)/(\lg q) < c$.   structure            |           concat           | approx split | sloppy split==================================================================================doubly-linked lists     |            O(1)            |     O(n)     |      *arrays                  |           O(n+m)           |     O(1)     |      *weight balanced trees   |         O(lg (n+m))        |     O(1)     |      *treaps and skip lists   |       O(lg min(n,m)) **    |   O(1) **    |     *,**functional finger trees |  O(min(lg lg m/n, lg lg n) |   O(lg n)    |     O(1)*: same as approx split**: expectedBy functional finger trees I mean Purely functional representations of catenable sorted lists by Kaplan and Tarjan.
Sequences with sublogarithmic concat and approximate split
ds.data structures