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