Cartesian tree - Codeforces

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	142
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

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://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8602

http://book.huihoo.com/pdf/cs-373-combinatorial-algorithms/notes/04-treaps.pdf

http://infoarena.ro/treapuri (a different implementation)

http://habrahabr.ru/blogs/algorithm/101818/
http://habrahabr.ru/blogs/algorithm/102006/
http://habrahabr.ru/blogs/algorithm/102364/

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.

Problems:

http://acm.timus.ru/problem.aspx?space=1&num=1439
http://acm.timus.ru/problem.aspx?space=1&num=1469
http://acm.timus.ru/problem.aspx?space=1&num=1521
http://acm.timus.ru/problem.aspx?space=1&num=1839
http://www.spoj.pl/problems/CERC07S/
http://www.spoj.pl/problems/ORDERSET/
http://acm.sgu.ru/problem.php?contest=0&problem=155
http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=1974&chapterid=2789
http://www.codechef.com/problems/GENETICS/

Комментарии (19)

Показать архивные | Написать комментарий?

alik

14 лет назад, скрыть # |

here

→ Ответить

daftcoder

From here: http://mirror.codeforces.com/blog/entry/608
http://habrahabr.ru/blogs/algorithm/101818/
http://habrahabr.ru/blogs/algorithm/102006/
http://habrahabr.ru/blogs/algorithm/102364/

Shinta

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

cr.rusucosmin

12 лет назад, скрыть # |

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!

adamant

12 лет назад, скрыть # ^ |

N≤10⁹
NlogN

Ok.

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.

Lord_F

← Rev. 2 →

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.

Thank you, I'll search about coordinates compression.

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

forthright48

11 лет назад, скрыть # ^ |

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

PraveenDhinwa

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

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

pimenta

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.