5
$\begingroup$

Given an array of $n$ elements, $A[n]$ consider a data-structure which supports the following operations:

You are allowed a one time $\mathcal{O}(n)$ preprocessing step:

  • $\text{Init}(A)$

And the operations

  • $\text{Reverse}(i,j)$: Reverse the slice $A[i \dots j]$ i.e. swap $A[i]$ with $A[j]$, $A[i+1]$ with $A[j-1]$ etc.
  • $\text{Retreive}(i)$: Returns the element at position $i$ in the array.

Now I have heard that there is a data-structure which supports both $\text{Reverse}$ and $\text{Retrieve}$ in guaranteed $\mathcal{O}(P(\log n))$ time, where $P(x)$ is a polynomial (Assume $\mathcal{O}(1)$ array accesses).

I am guessing this was published somewhere. Does anyone know any reference?

Apologies if this is actually at the level of undergraduate homework. Please feel free to close/delete it in that case (but please do provide a reference to the appropriate text/website in comments before deleting).

$\endgroup$
  • 1
    $\begingroup$ Now that this question has been answered (O(lg n) worst-case possible), I am wondering if there is a data structure with O(lg n) for one operation and o(lg n) for the other. $\endgroup$ – jbapple Apr 2 '11 at 2:58
10
$\begingroup$

Splay trees can easily do this, with their nodes augmented to have two extra pieces of information: the total number of descendants of each node (so you can answer retrieve queries), and a reverse bit, such that the roles of the left and right pointers at node x are reversed if x and its ancestors have an odd number of reverse bits. The amortized time per operation would be O(log n).

Whenever the tree is rotated it is possible to update this extra information in constant time (and maintain consistency of the reverse bits so that each node has the same parity of ancestral reverse bits as it did before the rotation). To handle a retrieve, just do a binary search down through the tree using the number-of-descendants of the left subtree at each step to determine whether to go left or right (and then as with any splay tree operation, splay up the node found by the retrieve). To handle a reverse operation, split the splay tree at i and j to form three trees, flip the reverse bit of the root of the middle tree, and concatenate them back together again.

I'm not sure of a published reference but looking through the splay tree literature might work. The one I'd try first is Tarjan's Data Structures and Network Algorithms, but I don't have time right now to check it.

$\endgroup$
  • $\begingroup$ Sorry, I was talking about a structure with guaranteed $O(P(\log n))$ operations. I will edit the question. +1 though. Thanks. $\endgroup$ – Aryabhata Apr 1 '11 at 21:59
  • 1
    $\begingroup$ @Moron: I think that the same idea works for any balanced binary (or bounded-degree) tree with O(log n)-time split and join operations such as AVL tree, 2-3 tree, red-black tree and so on. They give worst-case O(log n) time for Reverse and Retrieve unless I am missing something. $\endgroup$ – Tsuyoshi Ito Apr 1 '11 at 22:29
  • $\begingroup$ @Tsu: Hmm.. I will need some time to think about it, meanwhile would you mind adding an answer? $\endgroup$ – Aryabhata Apr 1 '11 at 22:33
  • $\begingroup$ @Moron: (1) I do not think that I can add anything to David’s nice answer, which contains everything that is needed. Just replace the splay tree with a red-black tree and it should do the job. (2) I realized that I am not sure if AVL trees support O(log n)-time split (although they probably do). I am sure that red-black trees do because that is what I looked for in Tarjan’s book when I posted the other answer which I gave a link to in my previous comment. $\endgroup$ – Tsuyoshi Ito Apr 1 '11 at 22:45
  • $\begingroup$ @Tsu: I just wanted the content to be in an answer, rather than comments, but I guess it is fine as it is. Thanks. $\endgroup$ – Aryabhata Apr 1 '11 at 22:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.