# Maintaining an array under subarray reversals

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.

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... */ }