2
$\begingroup$

Given a sequence of real numbers $\{a_1, a_2, a_3 \ldots a_n\}$, I wish to design a data structure that supports the following operations on it.

  1. $\mathrm{REVERSE}(i,j):$ Reverse the contiguous subsequence $a_i, a_{i+1}\ldots a_j$ i.e. swap $a_i$ with $a_j$, $a_{i+1}$ with $a_{j-1}$ so on and so forth.
  2. $\mathrm{REPORT}(i):$ Report the $i$-th element of the sequence.

In my attempt so far I have tried to construct a binary tree each node of which maintains a composition of reversals of the underlying segment but it doesn't seem like this approach can work. Any help is appreciated.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

You can get both operations in $O(\log n)$ time with a binary tree. The idea is to store a boolean at each node indicating whether or not the entire subtree underneath the node is logically (not physically) reversed. You can then reverse a node in $O(1)$, by toggling the boolean.

Logical reversal is pretty easy to handle: any time you would descend into a node, check if the node is marked as reversed; if so, then swap and logically reverse its children.

Using this approach, we can adapt standard split/join primitives. And then, using split/join, we can implement REVERSE(i,j) like this:

  1. split at offsets i and j to produce three trees left, middle, and right,
  2. logically reverse middle by toggling the boolean at its root, and
  3. join the three trees.

This requires only $O(\log n)$ time on a balanced tree.


Here's some pseudocode. The implementation of REPORT should hopefully demonstrate how logical reversal is handled.

// elements of type T
type Tree<T> {
  elem: T,
  left: Tree<T>,
  right: Tree<T>,
  size: int,
  rev: bool
}


function TOGGLE(tree) {
  tree.rev = !(tree.rev);
  return tree;
}


// swap and toggle children, if necessary. O(1) time.
function NORMALIZE(tree) {
  if (tree.rev) {
    left = tree.left;
    right = tree.right;
    
    tree.left = TOGGLE(right);
    tree.right = TOGGLE(left);
    tree.rev = False;
  }
}


function REPORT(tree, i) {
  NORMALIZE(tree);

  if (i <= tree.left.size)
    return REPORT(tree.left, i);
  else if (i == tree.left.size + 1)
    return tree.elem;
  else
    return REPORT(tree.right, i - tree.left.size - 1);
}


function REVERSE(tree, i, j) {
  left, tmp = SPLIT(tree, i);
  middle, right = SPLIT(tmp, j-i+1);
  return JOIN(left, JOIN(TOGGLE(middle), right))
}


function SPLIT(tree, i) { /* omitted... */ }
function JOIN(tree1, tree2) { /* omitted... */ }
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.