Build data structure to perform reverse and report queries in poly-logn time

开发者_如何转开发

Given a sequence of n numbers, {a₁, a₂, a₃, …, a_n}. Build a data structure such that the following operations can be performed in poly-logn time.

1. Reverse(i, j):

   Reverse all the elements in the range i to j, as shown below:

   Original Sequence: <… a_i-1, a_i, a_i+1, …, a_j-1, a_j, a_j+1, …>

   Sequence after swap: <… a_i-1, a_j, a_j-1, …, a_i-1, a_i, a_j+1, …>

2. Report(i):

   Report the i-th element in the sequence, i.e. a_i.

Here, poly-logn means some power of log n. like log(n) · log(n) may be acceptable.

[Note: Thanks to Prof. Baswana for asking this question.]

I was thinking of using a binary tree, with a node augmented with a Left|Right indicator and the number of elements in this sub-tree.

• If the indicator is set to Left then begin by reading the left child, then read the right one
• Else (set to Right) then begin by reading the right child, then read the left one

The Report is fairly obvious: O(log n)

The Revert is slightly more complicated, and I am unsure if it'd really work.

The idea would be to "isolate" the sequence of elements to reverse in a particular sub-tree (the lowest possible). This subtree contains range [a..b] including [i..j]

• Reverse the minimum sub-tree that contains this sequence (change of the indicator)
• Apply the Revert operation to [a..i-1] and [j+1..b]

Not sure it really works though :/

EDIT:

The previous solution does not work :) I can't imagine a solution that does not rearrange the tree, and they do not respect the complexity requirements.

I'll leave this there in case it gives some idea to someone else, and I'll delete it afterward unless I find a solution myself.

Splay trees + your decorations get O(log n) amortized. The structural problems Matthieu encountered are dealt with by the fact that in O(log n) amortized time, we can change the root to any node we like.

(Note: this data structure is an important piece of local search algorithms for the Traveling Salesman Problem, where people have found that two- and three-level trees with high arity are more efficient in practice.)