# Array slice reversing data-structure

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

• 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 Apr 2 '11 at 2:58

• Sorry, I was talking about a structure with guaranteed $O(P(\log n))$ operations. I will edit the question. +1 though. Thanks. – Aryabhata Apr 1 '11 at 21:59