17
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.