Treap

日付: 11月 11, 2018

## Introduction
Treap = Tree + heap，也就是树堆，为BST中的每一个结点附加一个priority，在保证BST性质的同时，通过旋转等方法同时保证priority满足堆性质(父结点小于/大于子结点)。

## Implementation
Treap有两种主要实现方法，一种是通过旋转维护，另一种是通过分裂与合并维护。后者实现起来代码量更少，且功能更强。实现主要参考[Treap - Competitive Programming Algorithms](https://cp-algorithms.com/data_structures/treap.html)

### Basic Treap
```c++
namespace Treap {
using T = int;
struct Node { T x; Node *l = 0, *r = 0; int p = rand(), c = 1; Node(T x) : x(x) {} };
using P = Node *;

int cnt(P t) { return !t ? 0 : t->c; }
void up(P t) { if (t) t->c = 1 + cnt(t->l) + cnt(t->r); }
bool has(P t, T x) { return !t ? 0 : x == t->x ? 1 : has(x < t->x ? t->l : t->r, x); }
int index(P t, T x) { return !t ? 0 : x <= t->x ? index(t->l, x) : cnt(t->l) + 1 + index(t->r, x); }
int rindex(P t, T x) { return !t ? 0 : x >= t->x ? rindex(t->r, x) : cnt(t->r) + 1 + rindex(t->l, x); }
T at(P t, int i) { int u = cnt(t->l); return i == u ? t->x : i < u ? at(t->l, i) : at(t->r, i - ++u); }
void split(P t, T x, P &l, P &r) {
    !t ? void(l = r = 0) : x < t->x ?
    (r = t, split(t->l, x, l, r->l), up(r)) : (l = t, split(t->r, x, l->r, r), up(l));
}
void merge(P &t, P l, P r) {
    !l || !r ? void(t = l ? l : r) : l->p > r->p ?
    (merge(l->r, l->r, r), up(t = l)) : (merge(r->l, l, r->l), up(t = r));
}
void insert(P &t, T x) { P u, v; split(t, x, u, v); merge(u, u, new Node(x)); merge(t, u, v); }
void erase(P &t, T x) { if (t) t->x == x ? merge(t, t->l, t->r) : erase(x < t->x ? t->l : t->r, x), up(t); }
};
```
* `struct Node { T x; Node *l = 0, *r = 0; int p = rand(), c = 1; };`  树结点结构，其中`x`保存值，`l`和`r`是左右子树，`p`是堆的优先级，`c`是该结点子树中结点数量，用于计算第k大值等
* `int cnt(P t)` 辅助函数，返回树`t`的结点数
* `void up(P t)` 辅助函数，更新树`t`维护的信心(结点数量)，要保证其左右儿子的信息是正确的
* `bool has(P t, T x)` 查询`x`是否在树t中出现，和普通BST相同
* `int index(P t, T x)` 计数树`t`中比`x`小的值，利用`cnt`计算
* `int rindex(P t, T x)` 计数树`t`中比`x`大的值，利用`cnt`计算
* `T at(P t, int i)` 查询树`t`中从小到大第`i`个值，下标从0开始
* `void split(P t, T x, P &l, P &r)` 核心函数，将树`t`分裂为`l`和`r`，保证`r`中的值大于`x`，`l`中的值不大于`x`
* `void merge(P &t, P l, P r)` 核心函数，将树`l`和`r`合并到`t`中，保证`l`中的元素小于`r`中的元素。在合并时根据`l`和`r`的优先级合并，保证堆性质
* `void insert(P &t, T x)` 将`x`插入到树`t`中，利用`split`/`merge`实现。先把`t`在`x`处分开，然后把左子树与新插入结点合并，最后把左右子树合并到`t`即可。因为是调用`merge`合并，堆性质得到保障
* `void erase(P &t, T x)` 把树`t`中的`x`删除(如果有多个只会删除一个)。按照BST性质找到一个值等于`x`的结点`u`，将其左右儿子合并到`u`，就把`u`从树中删除了

其他的一些常用操作，可以由以上操作组合，如
* 求x出现的次数，`cnt(t,x) - index(t, x) - rindex(t, x)`
* 求最大的小于x的数(前驱)，`at(t, index(x)-1)`
* 求最小的大于x的数(后继)，`at(t, cnt(t) - rindex(x))`

### Persistent
```c++
namespace PTreap {
using T = int;
struct Node { T x; Node *l = 0, *r = 0; int p = rand(), c = 1; Node(T x) : x(x) {} };
using P = Node *;

### Implicit Key
```c++
namespace ITreap {
using T = int;
struct Node { T x; Node *l = 0, *r = 0; int p = rand(), c = 1; bool b = 0; Node(T x) : x(x) {} };
using P = Node *;

int cnt(P t) { return !t ? 0 : t->c; }
void up(P t) { if (t) t->c = 1 + cnt(t->l) + cnt(t->r); }
void push(P t) { if (t && t->b) {t->b = 0, swap(t->l, t->r); if (t->l) t->l->b ^= 1; if (t->r) t->r->b ^= 1;}}
T at(P t, int i) { push(t); int u = cnt(t->l); return i == u ? t->x : i < u ? at(t->l, i) : at(t->r, i - ++u); }
void split(P t, P &l, P &r, int k, int a = 0) {
    !t ? void(l = r = 0) : (push(t), k <= a + cnt(t->l)) ?
    (r = t, split(t->l, l, r->l, k, a), up(r)) :
    (l = t, split(t->r, l->r, r, k, a + 1 + cnt(t->l)), up(l));
}
void merge(P &t, P l, P r) {
    push(l), push(r), !l || !r ? void(t = l ? l : r) : l->p > r->p ?
    (merge(l->r, l->r, r), up(t = l)) : (merge(r->l, l, r->l), up(t = r));
}
void insert(P &t, int i, T x) { P u, v; split(t, u, v, i); merge(u, u, new Node(x)); merge(t, u, v); }
void erase(P &t, int i) {
    if (t) cnt(t->l) == i ? merge(t, t->l, t->r) :
        cnt(t->l) > i ? erase(t->l, i) : erase(t->r, i - cnt(t->l) - 1), up(t);
}
void reverse(P &t, int l, int r) {
    P u, v, w;
    split(t, u, v, l), split(v, v, w, r - l);
    v->b ^= 1, merge(t, u, v), merge(t, t, w);
}
};
```
和基本Treap类似，可以当作一个数组使用。包含了隐式的一个key，即数组的下标。可以在$log(n)$时间内实现数组任意位置的访问，插入，删除与区间翻转。

KONGROOの基地

このブログを検索

Treap

コメント

コメントを投稿