# Sequences with sublogarithmic concat and approximate split

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
**: expected


By functional finger trees I mean "Purely functional representations of catenable sorted lists" by Kaplan and Tarjan.