Cartesian tree - Codeforces

Cartesian tree - Codeforces

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.

Read full article from Cartesian tree - Codeforces