sbasrik's blog

Treap
By sbasrik, 11 years ago, In English

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

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I know good article here, but it in Russian.

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 7   Vote: I like it +5 Vote: I do not like it

      Here's what I think badguy meant:

      Let a be the array you need to simulate.

      In the treap (call it T), each node corresponds to an element of a. For a node x_i corresponding to a_i, x_i's tree value is i, and x_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 T with 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 T into three treaps, T1, T2, an T3, where all elements of T1 are left of the range, elements of T2 are in the range, and elements of T3 are right of the range.

      Toggle the reverse bit in T2's root.

      Merge T1, T2, and T3 back into T.

      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).

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        An important correction: heap key of x_i is not 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.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Thanks for the correction, it seems I was confused :)

          → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +16 Vote: I do not like it

        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.

        → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank you all guys for the explanations and links.

→ Reply