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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.