-2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, you are right, it's better to call it update or operation, I will edit the question now. $\endgroup$ – someone12321 Jan 23 '18 at 21:32
  • $\begingroup$ What are your needs complexity wise ? Also, what are usually the values of $r_i - l_i$ and $N$, compared ? $\endgroup$ – wazdra Jan 23 '18 at 23:33
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Jan 24 '18 at 0:28
  • $\begingroup$ The complexity for each operation should be O(log(n)), O(log(n)) or even O(sqrt(n)) with some strange sqrt decomposition. $\endgroup$ – someone12321 Jan 24 '18 at 6:02
  • $\begingroup$ 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. $\endgroup$ – someone12321 Jan 24 '18 at 6:10
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can we do anything faster than linear, O(N) time? $\endgroup$ – someone12321 Jan 24 '18 at 6:04

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.