MarioYC's blog

Cartesian tree
By MarioYC, 13 years ago, In English
Today I read about cartesian tree(treap) from e-maxx's page, since it is in russian I decided to translate some parts.

Also here are some related links:

http://infoarena.ro/treapuri (a different implementation)
I would appreciate if someone could post problems that can be solved it, there are some at infoarena.

Cartesian tree (Treap):


A data structure that stores a pair (X,Y) in the form of a binary search tree with respect to X and a heap with respect to Y.

Assuming that al X and Y are different, for an element (X0,Y0):

- All the elements in the left subtree are such that X < X0
- All the elements in the right substree are such that X > X0
- All the elements in the left or right subtrees are such that Y < Y0

Notation:

X's are the keys.
Y's are the priorites (choosed at random)

Advantages:

If we didn't use priorities, then it would be a normal binary search tree, and the given set of X's could meet a lot of trees, some of which are degenerate
(for example in form of a chain), so operations would be done really slowly.

Priorities can uniquely identidy a tree that will be built. On average using priorites provides us the asymptotics O(log n).

Operations:

- Insert(X,Y), Avg Complexity O(log N) : Inserts a new item, we could also not pass Y as a parameter, instead we can choose it a random inside
- Search(X), Avg Complexity O(log N) : Searches for the element with the specified key value X
- Erase(X), Avg Complexity O(log N) : Searches for the element X and erases it
- Build(X1,...,XN), Avg Complexity O(N log N) : Builds a tree of a list of values
- Union(T1,T2), Avg Complexity O(M log N/M) : Combines two trees, assuming that the elements are different
- Intersect(T1,T2), Avg Complexity O(M log N/M) : Finds the common elements of two trees

Description of the implementation:

- Each element (X,Y) contains pointers to the left (L) an the right (R) sons.
- To implement other operations we require two commplementary operations: Split and Merge
- Split(T,X) : divides the tree T into two trees L and R so that L contains all elements that are smaller than X, and R contains all elements that area are equal or larger than X.
  This operation is performed in O(log N)

- Merge(T1,T2) : combines two subtrees T1 and T2, and returns a new tree. This operation is also implemented in O(log N). It works on the assumption that T1 and T2 have the
  appropiate order (all X values in the first are less than values at the second)

Implicit Cartesian Tree:


It is a simple modification of the usual Cartesian tree. It can be thought of as array on which you can implement the following procedures (complexity O(log N) online):

- Insert an element in the array at any position
- Removal of any element
- Sum, minimum, maximum of an arbitrary interval
- The addition, paint on the interval
- Reverse of an interval

The key idea is to use the indices of elements in the array as the key. However, these values are explicitely stored key.
The key of a node is the number number of nodes in its left subtree, and also, in the left subtree of its ancestors.
  • Vote: I like it
  • +30
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You should also mention that cartesian tress can also be used with lazy propagation as a super powerful and dynamic segment tree.

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

Can please someone explain me how to solve timus 1439? Right now I'm using a Treap but I'm still getting TLE. My complexity is O(N * log(N) + M * log(N)).

Here's my code :http://ideone.com/GKFzpd Thanks in advice!

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

    N≤109

    NlogN

    Ok.

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

      Please give me a hint, as I said, I'm stuck.. should I give up on the Treap? The N log N comes from the building of the treap.

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

        Treap is not efficient in this problem. Moreover, no data structure is efficient (I believe) if used in a naive way, because N is too big.
        I'd suggest coordinates compression and then Segment Tree or BIT.

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

          Thank you, I'll search about coordinates compression.

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

          Coordinates compression doesn't work in this problem for some reason. At least I couldn't implement it correct here.

          But we can keep only numbers of deleted doors in BST and use it to get answer. Or we can use compressed Segment Tree (as described here).

          Anyway here is the quite fast solution with Segment Tree which works in O(nlogn).

          → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got AC using Treap and Binary Search. So don't give up on Treap.

        Here is your hint: Suppose n = 10, out of which door number 3, 6,7 and 9 has been destroyed. 

        1 2 3 4 5 6 7 8 9 10    
    x     x x   x

        What will be the new number of these doors then? For example, 8. Since there are 3 doors (3,6,7) less than 8 which got destroyed, 8 will now become 5. Using this concept, each door x will become x — (number of doors <= x that got destroyed).

        So renumbered array would be: 1 2 2 3 4 4 4 5 5 6

        I think these hints are enough to solve the problem. When you have to destroy a door X, just find the original door number using binary search. For example, which door will be 4th door above? Door number 5.

        How many doors less than x has been destroyed can be found from treap in O(logN).

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

Could you please tell in the line "Union(T1,T2), Avg Complexity O(M log N/M) : Combines two trees, assuming that the elements are different", what M refers? Is it max (|T1|, |T2|)?

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

"The key idea is to use the indices of elements in the array as the key. However, these values are explicitely stored key. The key of a node is the number number of nodes in its left subtree, and also, in the left subtree of its ancestors. "

Could you please explain the last line, Please also correct the grammar of the sentence, especially the second part.

What is the difference between implicit and normal cartesian tree? I did not understood the meaning of using "implicit" keyword for array based cartesian tree?

In line "Split(T,X) : divides the tree T into two trees L and R so that L contains all elements that are smaller than X, and R contains all elements that area are equal or larger than X.", word "area" should be "are". Please edit that too.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the original article (on e-maxx) suggests that the BST is implicit, because the key is implicit. in traditional BSTs, the key you pass to an access operation is compared with a key stored in the current node being visited. when the BST uses an implicit key, the key you pass to an access operation is compared with a key calculated inside the operation, referring to some property of the current node being visited.

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

http://www.spoj.com/problems/QMAX3VN/

http://www.spoj.com/problems/CARDSHUF/

http://www.spoj.com/problems/STRLCP/

http://www.spoj.com/problems/TREAP/

http://www.spoj.com/problems/QUE2/

http://www.spoj.com/problems/KPMATRIX/

http://www.spoj.com/problems/CTRICK/

http://www.spoj.com/problems/GSS6/

http://www.spoj.com/problems/ANARC08H/

if i found more in my list i will add them also ...

but in contests using coordinate compression and segment tree / BIT is more useful and faster in code (if they are acceptable)

good luck solving them ...

→ Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

https://community.topcoder.com/stat?c=problem_statement&pm=14084

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

Is there any problem which needs treap for solving efficiently?

→ Reply