Anyone has any document or knowledge about performing reverse operation in segment tree by using treap ? There is a problem in Codechef that is required to do it, treap is mentioned but isn't explained in the tuttorial. Link to problem: http://www.codechef.com/problems/PALINDR

I know good article here, but it in Russian.

It was very helpful.

Basically, you create a normal treap, where the key of each tree node is the index of that element in your sequence, rather than the value. Since you can merge two treaps where the keys of one treap are all smaller than the keys of the other in O(log n) and do the inverse split operation in the same, you get an extremely flexible implementation of the normal array data structure.

Reversing a subsegment in O(log n) now basically just comes down to using lazy propagation to set a reverse bit on the nodes that represent the subsegment you're interested in. This is just a matter of cutting the subsegment out of the original array, setting the reverse bit on the root of the tree node which represents it, and then sticking the three treaps that you're left with back together.

The best resource in English that I've found for this is a Google translated version of the e-maxx article on the subject:

http://e-maxx.ru/algo/treap

Usually this is called 'implicit key treap', since when implementing it it makes sense to not store the actual array index as a key, but rather implicitly in each node as the count of the number of nodes in the node's left subtree (i.e. the number of keys smaller than that key).

It's worthwhile to note that you can do this with any binary search tree that support the merge and split described above. Splay trees are another popular choice. They are faster as well, but less elegant to implement.

First, thank you for replying. What do you mean by 'reverse bit'. And how do three traps occur ? Would you mind if you define the process more exhaustively.

Here's what I think badguy meant:

Let

abe the array you need to simulate.In the treap (call it

T), each node corresponds to an element ofa. For a nodex_icorresponding toa_i,x_i's tree value isi, andx_i's heap key is~~a_i~~still a random number [corrected thanks to Gassa]. Now, the treap is what badguy's link calls an~~"implicit cartesian tree"~~"treap with implicit keys" (at least according to Google Translate).Augment each node of

Twith a boolean (call it reverse). Whenever you encounter a node with reverse set, swap its children and toggle their reverse bits. This is just lazy propagation, if you've done that with a segment tree or something.Now, to reverse a range:

Split

Tinto three treaps,T1,T2, anT3, where all elements ofT1are left of the range, elements ofT2are in the range, and elements ofT3are right of the range.Toggle the reverse bit in

T2's root.Merge

T1,T2, andT3back intoT.Note that since we only update the reverse bits when necessary, this operation remains O(log N).

Edit: It now appears that "implicit Cartesian tree" may be a mistranslation of "treap with implicit keys" (the keys are implicit because they are indices, not values). I had confused treaps with Cartesian trees, which don't support the necessary operations in O(log N).An important correction: heap key of

`x_i`

isnot`a_i`

but a random number, as usual. Heap keys play an auxiliary role and can be substituted by some other balancing mechanism in`merge`

, regardless of whether a Cartesian tree is explicit or implicit.Thanks for the correction, it seems I was confused :)

Ah, it's good that you brought up the difference between a Cartesian tree and a treap. It seems in Russian competitive programming literature these names are used interchangeably, and in fact in these Russian texts when they say "Cartesian tree", they really mean treap.

A Cartesian tree is just a binary tree on a sequence of pairs that is heap-ordered on one of the elements of each pair, and BST-ordered on the other element. If you assign random values to each heap-ordered element, then the expected height of the resulting Cartesian tree is O(log n). This is the entire idea behind treaps. A treap is a Cartesian tree, and a Cartesian tree can be a treap, but it doesn't have to be.

The distinction is small in practice, but it's important to clarify terminology, especially since there are famous results on Cartesian trees that don't really apply to treaps, such as constant time query RMQ.

Another documentation of Treap

Thank you all guys for the explanations and links.