Obtain data structure able to do reverse range updates

For given array $A$ of size $N$, note that the array is going to be permutation of the numbers from 1 to N, each number will be there exactly once, we want to obtain data structure being able to perform two types of operations.

A. Update operation: Reverse the elements in the range $A[l_i \dots r_i]$

B. Query operation: Find the index of element $x$.

My thinking was to build segment tree, but the reverse query is hard to do, then I was thinking about implementing a balanced interval tree, and reversing the nodes, but the problem is balancing the tree, which is too slow.

• Yes, you are right, it's better to call it update or operation, I will edit the question now. Jan 23 '18 at 21:32
• What are your needs complexity wise ? Also, what are usually the values of $r_i - l_i$ and $N$, compared ? Jan 23 '18 at 23:33
• I think you can use the data structure described here to solve your problem: cs.stackexchange.com/q/16467/755. What's the context where you encountered this? Can you credit the source or explain the motivation?
– D.W.
Jan 24 '18 at 0:28
• The complexity for each operation should be O(log(n)), O(log(n)) or even O(sqrt(n)) with some strange sqrt decomposition. Jan 24 '18 at 6:02
• Also, how can we implement the find operation in the interval tree described in that post. Also, I forgot to write that the array is going to be permutation of numbers from 1 to N. Jan 24 '18 at 6:10

1 Answer

So I have two ideas, one is more mathy than the other.

Double linked list

You can use a custom made double linked list, in which nodes also have a boolean field reverse, set to false by default.

When going through the list, every time a node has reverse field true, you start going backward (when supposed to go right, you go left), until you encounter a true valued reverse field again.

To reverse a range from $i$ to $j$, you go to $i$ from the start and retrieve the actual state of walkthrough (LtR or RtL). You do the same for $j$. You accordingly reconnect $i$ to $j+1$ and $j$ to $i-1$ (they are 16 cases to handle if I'm not mistaking). Finally, i.reverse <- !i.reverse, same for $j$, and you're done !

To get the index of element $x$, you just have to look for $x$ while going through the list.

Complexity :

• Update operation $(i,j)$ : $O(j)$
• Find $x$ : $O(k)$ where $k$ is the index of $x$.

So both are in $O(n)$ in worst case.

An array and permutations

You just keep an array and a permutation $\sigma\in \mathfrak S_n$. You'll find ways to encode them in the link. Whenever you have to reverse from $i$ to $j$, you do the following : $$\sigma \gets \begin{pmatrix} 1 & 2 & \cdots & i-1 & i & i+1 &\cdots & j-1 & j&j+1 &\cdots & n\\ 1 & 2 &\cdots & i-1 & j & j-1 & \cdots & i+1 & i & j+1 & \cdots & n\end{pmatrix}\cdot\sigma$$ This multiplication can be done in $O(n)$. Read is then constant time. Finding an element can be in $O(\log n)$, if you sort the array and keep it's starting permutation in $\sigma$ at the start.

• Can we do anything faster than linear, O(N) time? Jan 24 '18 at 6:04