Treap - Resources

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Resources/Data Structures/Treap

Treap

Introduction

A treap is a data structure that combines a binary search tree and a binary heap. The name comes from tree + heap.

More precisely, a treap stores pairs $(X, Y)$ so that:

it is a binary search tree by $X$ ;
it is a heap by $Y$ .

So if a node contains $(X_0, Y_0)$ , then:

Y0

)

all nodes in the left subtree have keys $X < X_0$ ;
all nodes in the right subtree have keys $X > X_0$ ;
all nodes in both subtrees have priorities $Y \leq Y_0$ .

Treaps support the following operations:

Insert $(X, Y)$ in $O(\log N)$
Add a new node to the tree. In practice, we usually pass only $X$ and generate $Y$ randomly.
Search $(X)$ in $O(\log N)$
Search for a node with key $X$ . This works exactly like in a usual binary search tree.
Erase $(X)$ in $O(\log N)$
Remove the node with key $X$ .
Build $(X_1, X_2, \ldots, X_N)$ in $O(N)$ Build a treap from a sorted list of keys.

Implicit Treaps

An implicit treap is a modification of a usual treap where the keys are not stored explicitly.

Instead, the position of a node in the array is determined by the sizes of subtrees. Because of this, an implicit treap can be viewed as a dynamic array that supports many operations efficiently in online mode.

For an array $A_1, A_2, \ldots, A_N$ , an implicit treap can support:

Insert $(i, X)$
Insert a new element $X$ at position $i$ , where $0 \leq i \leq N$ .
Erase $(i)$
Delete the element at position $i$ .
Get $(l, r)$
Compute the sum, minimum, maximum, or other information on the interval $[l, r]$ .
Update $(l, r)$
Apply an update on the interval $[l, r]$ , for example add a value or repaint the segment.
Reverse $(l, r)$
Reverse the subarray on the interval $[l, r]$ .
Swap $(l_1, r_1, l_2, r_2)$ Swap two subarrays.

This makes implicit treaps very powerful for sequence problems.

Implementation

Each node stores:

key x
priority y
pointer to the left child l
pointer to the right child r

We implement all main treap operations using just two auxiliary operations:

Split
Merge

Split

Split(T, X) divides the tree T into two subtrees L and R such that:

L contains all keys < X
R contains all keys >= X

This operation works in $O(\log N)$ .

Idea

Suppose the root of the current tree is v.

If v->x < X, then v must belong to the left part.
We recursively split the right subtree.
Otherwise, v must belong to the right part.
We recursively split the left subtree.

Merge

Merge(T_1, T_2) combines two trees T_1 and T_2 into one tree.

This operation assumes that all keys in T_1 are smaller than all keys in T_2.

It also works in $O(\log N)$ .

Idea

To preserve the heap property by priority:

if the root of T_1 has larger priority, it becomes the root;
otherwise, the root of T_2 becomes the root.

Then we recursively merge the remaining subtree.

Implicit Treaps

In an implicit treap, the key of a node is its position in the array, but we do not store this value directly.

Instead, we maintain the size of each subtree.

The implicit key of a node is determined by:

the number of nodes in its left subtree;
plus contributions from ancestors when the node lies in a right subtree.

Because all operations move down the tree, we can compute positions using subtree sizes.

So we add one more field:

cnt — the size of the subtree

Helper Functions

Split and Merge for Implicit Treap

Now split(v, l, r, x) splits by position: the left part gets the first x elements.

O(N)

)

struct treap {
    treap *l, *r;
    int x, y;

    treap(int _x) : l(NULL), r(NULL), x(_x), y(rng()) {}
};

typedef treap* tree;

void split(tree v, tree &l, tree &r, int x) {
    if (v == NULL) {
        l = r = NULL;
        return;
    } else if (v->x < x) {
        split(v->r, v->r, r, x);
        l = v;
    } else {
        split(v->l, l, v->l, x);
        r = v;
    }
}

tree merge(tree l, tree r) {
    if (l == NULL) {
        return r;
    } else if (r == NULL) {
        return l;
    } else if (l->y > r->y) {
        l->r = merge(l->r, r);
        return l;
    } else {
        r->l = merge(l, r->l);
        return r;
    }
}

int get_cnt(tree v) {
    return (v ? v->cnt : 0);
}

void upd_cnt(tree v) {
    v->cnt = 1;
    v->cnt += (v->l ? v->l->cnt : 0);
    v->cnt += (v->r ? v->r->cnt : 0);
}

void split(tree v, tree &l, tree &r, int x) {
    if (v == NULL) {
        l = r = NULL;
        return;
    }
    if (get_cnt(v->l) < x) {
        split(v->r, v->r, r, x - get_cnt(v->l) - 1);
        l = v;
        upd_cnt(l);
    } else {
        split(v->l, l, v->l, x);
        r = v;
        upd_cnt(r);
    }
}

tree merge(tree l, tree r) {
    if (l == NULL) {
        return r;
    } else if (r == NULL) {
        return l;
    }
    if (l->y > r->y) {
        l->r = merge(l->r, r);
        upd_cnt(l);
        return l;
    } else {
        r->l = merge(l, r->l);
        upd_cnt(r);
        return r;
    }
}