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.
