Treap
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
// 不带size域的treap
class Treap {
public:
const static int MaxN = 100000;
int root, tsize, l[MaxN], r[MaxN], p[MaxN];
int key[MaxN];
void rot_l(int &x) { //before using this function, please ensure that the right son of x exist
int tmp = r[x];
r[x] = l[tmp]; l[tmp] = x;
x = tmp;
}
void rot_r(int &x) { //before using this function, please ensure that the left son of x exist
int tmp = l[x];
l[x] = r[tmp]; r[tmp] = x;
x = tmp;
}
Treap():root(-1),tsize(-1) {}
void insert(int &root, const int &x) {
if(root == -1) {
key[++tsize] = x;
root = tsize;
p[root] = rand();
l[root] = r[root] = -1;
}
else if(x <= key[root]) {
insert(l[root], x);
if(p[l[root]] > p[root]) rot_r(root);
}
else {
insert(r[root], x);
if(p[r[root]] > p[root]) rot_l(root);
}
}
void del(int &root, const int &x) {
if(key[root] == x) {
if(l[root]==-1 && r[root]==-1) root = -1;
else if(l[root] == -1) root = r[root];
else if(r[root] == -1) root = l[root];
else {
if(p[l[root]] > p[r[root]]) {
rot_r(root);
del(r[root], x);
}
else {
rot_l(root);
del(l[root], x);
}
}
}
else if(x < key[root]) del(l[root], x);
else del(r[root], x);
}
bool find(int &root, const int &x) {
if(root == -1) return false;
if(x == key[root]) return true;
else if(x < key[root]) return find(l[root], x);
else return find(r[root], x);
}
};
18. 带size域的treap
//带size的treap
class Treap {
public:
const static int MaxN = 100000;
int root, tsize, l[MaxN], r[MaxN], p[MaxN], nsize[MaxN];
int key[MaxN];
void maintain(const int &root) {
int ta, tb;
ta = l[root]==-1? 0 : nsize[l[root]];
tb = r[root]==-1? 0 : nsize[r[root]];
nsize[root] = ta+tb+1;
}
void rot_l(int &x) { //before using this function, please ensure that the right son of x exist
int tmp = r[x];
r[x] = l[tmp]; maintain(x);
l[tmp] = x; x = tmp; maintain(x);
}
void rot_r(int &x) { //before using this function, please ensure that the left son of x exist
int tmp = l[x];
l[x] = r[tmp]; maintain(x);
r[tmp] = x; x = tmp; maintain(x);
}
Treap():root(-1),tsize(-1) {}
void insert(int &root, const int &x) {
if(root == -1) {
key[++tsize] = x;
root = tsize;
p[root] = rand();
l[root] = r[root] = -1;
nsize[root] = 1;
}
else if(x <= key[root]) {
insert(l[root], x);
if(p[l[root]] > p[root]) rot_r(root);
}
else {
insert(r[root], x);
if(p[r[root]] > p[root]) rot_l(root);
}
maintain(root);
}
void del(int &root, const int &x) {
if(key[root] == x) {
if(l[root]==-1 && r[root]==-1) root = -1;
else if(l[root] == -1) root = r[root];
else if(r[root] == -1) root = l[root];
else {
if(p[l[root]] > p[r[root]]) {
rot_r(root);
del(r[root], x);
}
else {
rot_l(root);
del(l[root], x);
}
}
}
else if(x < key[root]) del(l[root], x);
else del(r[root], x);
if(root != -1) maintain(root);
}
int kthElement(const int &root, int k) {
int ta;
ta = l[root]==-1? 0 : nsize[l[root]];
if(ta >= k) return kthElement(l[root], k);
else if(ta+1 == k) return key[root];
else return kthElement(r[root], k-ta-1);
}
bool find(int &root, const int &x) {
if(root == -1) return false;
if(x == key[root]) return true;
else if(x < key[root]) return find(l[root], x);
else return find(r[root], x);
}
};
}}}// 不带size域的treap
class Treap {
public:
const static int MaxN = 100000;
int root, tsize, l[MaxN], r[MaxN], p[MaxN];
int key[MaxN];
void rot_l(int &x) { //before using this function, please ensure that the right son of x exist
int tmp = r[x];
r[x] = l[tmp]; l[tmp] = x;
x = tmp;
}
void rot_r(int &x) { //before using this function, please ensure that the left son of x exist
int tmp = l[x];
l[x] = r[tmp]; r[tmp] = x;
x = tmp;
}
Treap():root(-1),tsize(-1) {}
void insert(int &root, const int &x) {
if(root == -1) {
key[++tsize] = x;
root = tsize;
p[root] = rand();
l[root] = r[root] = -1;
}
else if(x <= key[root]) {
insert(l[root], x);
if(p[l[root]] > p[root]) rot_r(root);
}
else {
insert(r[root], x);
if(p[r[root]] > p[root]) rot_l(root);
}
}
void del(int &root, const int &x) {
if(key[root] == x) {
if(l[root]==-1 && r[root]==-1) root = -1;
else if(l[root] == -1) root = r[root];
else if(r[root] == -1) root = l[root];
else {
if(p[l[root]] > p[r[root]]) {
rot_r(root);
del(r[root], x);
}
else {
rot_l(root);
del(l[root], x);
}
}
}
else if(x < key[root]) del(l[root], x);
else del(r[root], x);
}
bool find(int &root, const int &x) {
if(root == -1) return false;
if(x == key[root]) return true;
else if(x < key[root]) return find(l[root], x);
else return find(r[root], x);
}
};
18. 带size域的treap
//带size的treap
class Treap {
public:
const static int MaxN = 100000;
int root, tsize, l[MaxN], r[MaxN], p[MaxN], nsize[MaxN];
int key[MaxN];
void maintain(const int &root) {
int ta, tb;
ta = l[root]==-1? 0 : nsize[l[root]];
tb = r[root]==-1? 0 : nsize[r[root]];
nsize[root] = ta+tb+1;
}
void rot_l(int &x) { //before using this function, please ensure that the right son of x exist
int tmp = r[x];
r[x] = l[tmp]; maintain(x);
l[tmp] = x; x = tmp; maintain(x);
}
void rot_r(int &x) { //before using this function, please ensure that the left son of x exist
int tmp = l[x];
l[x] = r[tmp]; maintain(x);
r[tmp] = x; x = tmp; maintain(x);
}
Treap():root(-1),tsize(-1) {}
void insert(int &root, const int &x) {
if(root == -1) {
key[++tsize] = x;
root = tsize;
p[root] = rand();
l[root] = r[root] = -1;
nsize[root] = 1;
}
else if(x <= key[root]) {
insert(l[root], x);
if(p[l[root]] > p[root]) rot_r(root);
}
else {
insert(r[root], x);
if(p[r[root]] > p[root]) rot_l(root);
}
maintain(root);
}
void del(int &root, const int &x) {
if(key[root] == x) {
if(l[root]==-1 && r[root]==-1) root = -1;
else if(l[root] == -1) root = r[root];
else if(r[root] == -1) root = l[root];
else {
if(p[l[root]] > p[r[root]]) {
rot_r(root);
del(r[root], x);
}
else {
rot_l(root);
del(l[root], x);
}
}
}
else if(x < key[root]) del(l[root], x);
else del(r[root], x);
if(root != -1) maintain(root);
}
int kthElement(const int &root, int k) {
int ta;
ta = l[root]==-1? 0 : nsize[l[root]];
if(ta >= k) return kthElement(l[root], k);
else if(ta+1 == k) return key[root];
else return kthElement(r[root], k-ta-1);
}
bool find(int &root, const int &x) {
if(root == -1) return false;
if(x == key[root]) return true;
else if(x < key[root]) return find(l[root], x);
else return find(r[root], x);
}
};