上一篇：
Treap是一个玄学的平衡树
为什么说它玄学呢？ 还记得上一节说过每个平衡树都有自己的平衡方式吗？
没错，它平衡的方式是。。。。。。rand！！！！
注意，Treap是不依靠旋转平衡的！！
我认为它的思想是最好理解的，代码也简洁易懂（虽然慢了点）
而且灵活性较高，尤其是平衡树合并qwq
洛谷P3369普通平衡树跑了600多ms
\(\color{#9900ff}{定义}\)
struct node { node *ch[2]; int siz, val, key; node(int siz = 1, int val = 0, int key = rand()): siz(siz), val(val), key(key) { ch[0] = ch[1] = NULL; } void upd() { siz = (ch[0]? ch[0]->siz : 0) + (ch[1]? ch[1]->siz : 0) + 1; } int rk() { return ch[0]? ch[0]->siz + 1 : 1; }}pool[maxn], *tail, *root; siz为子树大小，val为点权，key为rand
\(\color{#9900ff}{基本操作}\)
1、split
split，顾名思义，就是分裂的意思
作用是把一棵树分裂成为两棵树
但是总不能随便分裂吧。。
因此，其内有4个参数
split（a，b，c，val）代表把以a为根的树分裂，分裂后的两棵树树根分别为b，c，保证树b上的所有节点权值\(\leq val\)，树c上的所有点权\(\geq val\)
要获得分裂后树的两根，所以a，b要传址，即split（node *a,node *&b,node *&c,int val）
放上代码
void split(node *o, node *&a, node *&b, int val) { if (!o) return (void)(a = b = NULL); //递归边界，当前位置为空，分裂后当然都为空 if (o->val <= val) a = o, split(o->ch[1], a->ch[1], b, val), a->upd(); //小于等于val的要在a里面，所以先直接让a=o，为什么呢 //既然o->val<=val,显然o的左子树所有值都小于val，因此这些点都是a的 //但是我们不能保证o右子树的所有点<=val，因此递归向下来构建a的右子树，本层对b无贡献，所以还是b else b = o, split(o->ch[0], a, b->ch[0], val), b->upd(); //同上 //别忘了维护性质 //a或b树会改变，所以要维护} 2、merge
merge，顾名思义，就是合并的意思
作用是把两棵树合并成为两棵树（有分裂就得有合并呗）
这回就是随便合并了。。。。。。
怎么随便合并呢？ 没错，rand！
其内有3个参数
merge（a，b，c）代表把以b，c为根的两棵树合并，合并后的树树根为a
要获得合并后树根，所以a要传址，即merge（node *&a,node *b,node *c）
放上代码
void merge(node *&o, node *a, node *b) { if (!a || !b) return (void)(o = a? a : b); //有一个为空，则等于另一个（如果另一个也是空其实就是空了） //这个key就是rand，不解释 //方法跟split差不多，这样也好记qwq //反正瞎搞总比不搞弄成一条链强。。。。。。 //这样就可以使极端情况尽量少 if (a->key <= b->key) o = a, merge(o->ch[1], a->ch[1], b); else o = b, merge(o->ch[0], a, b->ch[0]); o->upd(); //别忘了维护性质} 至此，基本操作已经完成（是不是很简单？）
\(\color{#9900ff}{其它操作}\)
1、插入
既然有了基本操作，肯定是不能暴力插了。。。
其实每个操作都要用到基本操作的（可见其重要性）
void ins(int val) { node *x = NULL, *y = NULL; //定义两个空节点 //作用：一会分裂的时候作为两棵树的根，起一个承接作用 node *z = new(tail++) node(1, val); //定义要插入的节点 split(root, x, y, val); //因为要保证平衡树的性质，所以插入的位置必须要合适 //我们把所有<=val的点都分给x，剩下的分给y //这样原来以root为根的数分成了两个 //我们要把z插进去 //怎么插♂呢 //可以把z一个点看成一棵树 //直接暴力合并就行了 merge(x, x, z); merge(root, x, y);}//没了？//没了！ 2、删除
删除其实也很简单，几乎就是围绕split，merge暴力操作
void del(int val) { node *x = NULL, *y = NULL, *z = NULL; split(root, x, y, val); split(x, x, z, val - 1); //树x的所有点权都小于val //树y的所有点权都大于val //综上，树z的点权等于val //所以。。。。。。 merge(z, z->ch[0], z->ch[1]); //我们只删除一个val，所以剩下的要合并，别忘了 merge(x, x, z); merge(root, x, y); //把分崩离析（<----瞎用成语）的树恢复原状} 3、查询数x的排名
排名，可以理解为比x小的数的个数+1（理解一下，这是解决此操作的关键）
所以我们要找到比x小的数的个数
int rnk(int val) { node *x = NULL, *y = NULL; split(root, x, y, val - 1); //把所有小于val的点分走 int t = (x? x->siz : 0) + 1; //注意判空 //x作为所有合法点的根，他的大小不正是我们要找的比val小的数的个数吗？ //加一就是排名！ merge(root,x,y); //不要过于兴奋，你的树还没有合并！！！！ return t;} 4、查询第k大的数
这个是唯一不借助基本操作的操作
node *kth(node *o, int k) { //第k大不就是排名为k的数么 //这不就是操作3的逆操作吗 while(o->rk() != k) { //暴力找 if(o->rk() < k) k -= o->rk(), o = o->ch[1]; //减去左边的贡献 else o = o->ch[0]; } return o;} 5、前驱
int pre(int val) { node *x = NULL, *y = NULL; split(root, x, y, val - 1); //分离所有小于y的数 node *z = kth(x, x->siz); //既然pre为小于val的数中最大的一个，我们就找x树中的最大的那个不就行了？ merge(root, x, y); return z->val;} 6、后继
int nxt(int val) { //跟上面只是稍稍有点不同而已 node *x = NULL, *y = NULL; split(root, x, y, val); //把所有小于等于val的点都分走，注意这里可以取等号！ //那么y中的点都大于val //在其中找最小的 node *z = kth(y, 1); merge(root, x, y); return z->val;} 没了。。。。。。
Treap就没了。。。。。。
放上完整代码
#include#define LL long longLL in() { char ch; LL x = 0, f = 1; while(!isdigit(ch = getchar()))(ch == '-') && (f = -f); for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48)); return x * f;}const int maxn = 1e5 + 5;struct Treap {protected: struct node { node *ch[2]; int siz, val, key; node(int siz = 1, int val = 0, int key = rand()): siz(siz), val(val), key(key) { ch[0] = ch[1] = NULL; } void upd() { siz = (ch[0]? ch[0]->siz : 0) + (ch[1]? ch[1]->siz : 0) + 1; } int rk() { return ch[0]? ch[0]->siz + 1 : 1; } }pool[maxn], *tail, *root; void split(node *o, node *&a, node *&b, int val) { if (!o) return (void)(a = b = NULL); if (o->val <= val) a = o, split(o->ch[1], a->ch[1], b, val), a->upd(); else b = o, split(o->ch[0], a, b->ch[0], val), b->upd(); } void merge(node *&o, node *a, node *b) { if (!a || !b) return (void)(o = a? a : b); if (a->key <= b->key) o = a, merge(o->ch[1], a->ch[1], b); else o = b, merge(o->ch[0], a, b->ch[0]); o->upd(); } node *kth(node *o, int k) { while(o->rk() != k) { if(o->rk() < k) k -= o->rk(), o = o->ch[1]; else o = o->ch[0]; } return o; }public: Treap() { root = NULL; tail = pool; } int rnk(int val) { node *x = NULL, *y = NULL; split(root, x, y, val - 1); int t = (x? x->siz : 0) + 1; merge(root, x, y); return t; } void ins(int val) { node *x = NULL, *y = NULL; node *z = new(tail++) node(1, val); split(root, x, y, val); merge(x, x, z); merge(root, x, y); } void del(int val) { node *x = NULL, *y = NULL, *z = NULL; split(root, x, y, val); split(x, x, z, val - 1); merge(z, z->ch[0], z->ch[1]); merge(x, x, z); merge(root, x, y); } int pre(int val) { node *x = NULL, *y = NULL; split(root, x, y, val - 1); node *z = kth(x, x->siz); merge(root, x, y); return z->val; } int nxt(int val) { node *x = NULL, *y = NULL; split(root, x, y, val); node *z = kth(y, 1); merge(root, x, y); return z->val; } int kth(int k) { return kth(root, k)->val; }}s;int main() { for(int p, T = in(); T --> 0;) { p = in(); if(p == 1) s.ins(in()); if(p == 2) s.del(in()); if(p == 3) printf("%d\n", s.rnk(in())); if(p == 4) printf("%d\n", s.kth(in())); if(p == 5) printf("%d\n", s.pre(in())); if(p == 6) printf("%d\n", s.nxt(in())); } return 0;}
下一篇：