<p>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).</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-04-01T21:59:47.310Z
Sorry, I was talking about a structure with guaranteed $O(P(\log n))$ operations. I will edit the question. +1 though. Thanks.
Aryabhata
CC BY-SA 2.5
2011-04-01T22:29:33.363Z
@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](http://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree/1166#1166) 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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-04-01T22:33:11.847Z
@Tsu: Hmm.. I will need some time to think about it, meanwhile would you mind adding an answer?
Aryabhata
CC BY-SA 2.5
2011-04-01T22:45:12.887Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-04-01T22:55:10.177Z
@Tsu: I just wanted the content to be in an answer, rather than comments, but I guess it is fine as it is. Thanks.
Aryabhata
CC BY-SA 2.5
2011-04-03T02:43:39.263Z
@Tsu / David: It does not look that obvious to me. Please humor me. Won't the split and join change the structure of the tree? How do we deal with the reverse bits during split and join? A possible information theoretic objection to this approach is that there are $\Omega(n^2)$ possible reverse operations, but you only store $O(n)$ bits of information. Thank you for your time.
Aryabhata
CC BY-SA 2.5
2011-04-03T07:22:56.083Z
@Moron: at any point in time, the structure of the tree is exactly a valid structure of a splay tree or red-black tree for the current sequence, but with a little indirection needed at each node to figure out where its real left and right child pointers are. The extra bits aren't what represents the sequence, the tree does; the extra bits are only there to save you from swapping a lot of pointers around. So as long as standard splay trees or red-black trees can handle split/join operations, so can this modified structure.
David Eppstein
CC BY-SA 2.5
2011-04-03T16:46:02.113Z
I am still a little unsure, but I won't bother you anymore :-). Thank you.
Aryabhata
CC BY-SA 2.5
2011-04-01T21:56:18.573Z
2011-04-01T21:56:18.573Z
David Eppstein
<p>Given an array of $n$ elements, $A[n]$ consider a data-structure which supports the following operations:</p>

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

<ul>
<li>$\text{Init}(A)$</li>
</ul>

<p>And the operations</p>

<ul>
<li>$\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. </li>
<li>$\text{Retreive}(i)$: Returns the element at position $i$ in the array. </li>
</ul>

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

<p>I am guessing this was published somewhere. Does anyone know any reference?</p>

<p>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).</p>

CC BY-SA 2.5
2011-04-02T02:58:42.297Z
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.
jbapple
<reference-request><ds.data-structures>
Array slice reversing data-structure
Aryabhata
# Array slice reversing data-structure

(Asked by: username_0 on 2011-04-01)

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).

**Tags:** reference-request, ds.data-structures
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-04-01. Score: 10

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.

> **Comments:**
> **username_0**: Sorry, I was talking about a structure with guaranteed $O(P(\log n))$ operations. I will edit the question. +1 though. Thanks.  
> **username_3**: @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](http://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree/1166#1166) 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.  
> **username_0**: @Tsu: Hmm.. I will need some time to think about it, meanwhile would you mind adding an answer?  
> **username_3**: @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.  
> **username_0**: @Tsu: I just wanted the content to be in an answer, rather than comments, but I guess it is fine as it is. Thanks.  
> **username_0**: @Tsu / David: It does not look that obvious to me. Please humor me. Won't the split and join change the structure of the tree? How do we deal with the reverse bits during split and join? A possible information theoretic objection to this approach is that there are $\Omega(n^2)$ possible reverse operations, but you only store $O(n)$ bits of information. Thank you for your time.  
> **username_2**: @Moron: at any point in time, the structure of the tree is exactly a valid structure of a splay tree or red-black tree for the current sequence, but with a little indirection needed at each node to figure out where its real left and right child pointers are. The extra bits aren't what represents the sequence, the tree does; the extra bits are only there to save you from swapping a lot of pointers around. So as long as standard splay trees or red-black trees can handle split/join operations, so can this modified structure.  
> **username_0**: I am still a little unsure, but I won't bother you anymore :-). Thank you.  

---

