非旋treap ( fhq treap )

学不懂splay，所以学了非旋treap
treap的效率其实和splay差不多

核心操作

fhq treap和treap同样有一个随机分配的rnd值，用于平衡 ( 在不改变性质的情况下，使树的形态趋于随机以保证平衡），但fhq treap不需要旋转操作来维持平衡，因为有两个神奇的操作merge（合并）和split（分裂）

1，分裂(split)

左小右大
1.按权值分裂
效果 ：将以某个节点为根的子树分裂为两个新的子树 , 这两个子树的根节点分别为x,y .
其中x为根的子树中所有点的权值均小于等于 v, y为根的子树中的所有点的权值均 大于 v.

操作：
对以now节点为根的子树 ：
1.now的权值小于等于v : 将now 与x连接，分裂右子树 （左儿子在此操作中接入了x）
2.now的权值大于v : 将now 与y连接，分裂左子树（右儿子在此操作中接入了y）
（split操作相当于将每个节点与新的左右儿子连接）
更新now
建议结合代码理解

void split(int now,int k,int &x,int &y){//注意观察&的用途if(!now) x=y=0;//结束else{if(tr[now].v<=k)x=now,split(tr[now].son[1],k,tr[now].son[1],y);//x=now相当于tr[祖先].son[1]=now ，右子树中剩下的委派给右儿子。（对祖先也是如此）elsey=now,split(tr[now].son[0],k,x,tr[now].son[0]);//y=now相当于tr[祖先].son[0]=now , 左子树中剩下的委派给左儿子。（对祖先也是如此）update(now);//更新 （ 因为这棵树已经“重构” ）}
}

解决区间问题的时候要按size分
这时k为size 若now树的左子树有>=k个节点，那么就从其左子树中找k个
否则，从其右子树中找k-tree[lson].size-1个（左边贡献了足够多的点） 减去的1是根节点（有点像treap求第k大）

void split(int now, int k, int &x, int &y) { // 前k个值组成x，k+1到最后一个值组成yif(!now) x = y = 0;else {if(tr[now].lz) down(now);if(k <= tr[tr[now].ls].siz) //画画图理解一下，k在now的左子树里就执行下面的语句y = now, split(tr[now].ls, k, x, tr[now].ls); //now及其右树已分到y上，现在分now的左子树，并且y的等待位置是y的左子节点else x = now, split(tr[now].rs, k-tr[tr[now].ls].siz-1, tr[now].rs, y);update(now);}
}

2.合并（merge）

递归的过程，在执行之前需要保证x中所有点的val值（要存储的值，不是随机值）都小于y的（简称为x < y），这是二叉搜索树的性质，而如何保证这个性质先不用着急，在插入操作中，这个性质自然实现了。最后要返回当前根节点

int merge(int x,int y){if(!x||!y) return x+y;//即返回非0的那个if(tr[x].rnd<tr[y].rnd){//rnd是随机因子tr[x].son[1]=merge(tr[x].son[1],y); //x为根update(x);return x;}else{tr[y].son[0]=merge(x,tr[y].son[0]);//y为根update(y);return y;} 
}

操作时注意实时维护root具体是哪个点

基本操作

1.建新节点

int new_code(int v)
{tot++;tr[tot].size=1;tr[tot].v=v;tr[tot].rnd=rand();return tot;
}

2.update

空节点不可update , 因为会使siz为1

int new_node(int v)
{tot++;tr[tot].size=1;tr[tot].v=v;tr[tot].rnd=rand();return tot;
}

3.插入

为了保证"x < y"这个性质，只好按val拆分，然后在合并x和点new的时候虽然x中有和new值相同的，但是问题不大。

split(root, val, x, y);
root = merge(merge(x, new_node(val)), y);

4.删除

注意合并的时候要反着拆分的顺序操作，仍然是为了保证"x < y"
下面的操作成功分出了一个c，而c的根的值一定为val，这是因为前面划分除出了一个a，a只有两种点，值为val的点和值<=val的点，而c又是从a中分出来的

split(root, val, a, b);
split(a, val-1, a, c);
c = merge(tree[c].lson, tree[c].rson);
root = merge(merge(a,c), b);//a，c最后拆，最先合

5.查询排名为k的数

int kth(int now,int k){while(1){if(k<=tr[tr[now].son[0]].size)//就向左now=tr[now].son[0];//查前驱时若前驱为空会在这里死循环，所以有时要设哨兵节点else{if(k==tr[tr[now].son[0]].size+1) return now;else{k-=tr[tr[now].son[0]].size+1;now=tr[now].son[1];//向右}}}
}

6.找值为val的rank

把整棵树以 val-1 split 分为x和y 然后答案就是x.size+1，当然前提是这个值存在

7.找val的前驱

按val-1划分，左树里面找最大的，即在左树里面找rank为左树size的即可

8.找val的后继

按val划分，右树rank为1的就是

P3369 【模板】普通平衡树.

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
struct trnode{int son[2],v,rnd,size;
}tr[N];
int tot = 0,root=0;void update(int x){tr[x].size=tr[tr[x].son[0]].size+tr[tr[x].son[1]].size+1;
}
int new_code(int v)
{tot++;tr[tot].size=1;tr[tot].v=v;tr[tot].rnd=rand();return tot;
}
int merge(int x,int y){if(!x||!y) return x+y;if(tr[x].rnd<tr[y].rnd){tr[x].son[1]=merge(tr[x].son[1],y);update(x);return x;}else{tr[y].son[0]=merge(x,tr[y].son[0]);update(y);return y;}
}
void split(int now,int k,int &x,int &y){if(!now) x=y=0;else{if(tr[now].v<=k)x=now,split(tr[now].son[1],k,tr[now].son[1],y);elsey=now,split(tr[now].son[0],k,x,tr[now].son[0]);update(now);}
}
int kth(int now,int k){while(1){if(k<=tr[tr[now].son[0]].size)now=tr[now].son[0];else{if(k==tr[tr[now].son[0]].size+1) return now;else{k-=tr[tr[now].son[0]].size+1;now=tr[now].son[1];}}}
}
int main(){srand(902);int T;int flag ,x,y,z,a,b;scanf("%d",&T);while(T--){scanf("%d%d",&flag,&a);if(flag==1){split(root,a,x,y);root=merge(merge(x,new_code(a)),y);}else if(flag == 2){split(root,a,x,z);split(x,a-1,x,y);y=merge(tr[y].son[0],tr[y].son[1]);root=merge(merge(x,y),z);}else if(flag==3){split(root,a-1,x,y);printf("%d\n",tr[x].size+1);root=merge(x,y);}else if(flag==4)printf("%d\n",tr[kth(root,a)].v);else if(flag==5){split(root,a-1,x,y);printf("%d\n",tr[kth(x,tr[x].size)].v);root=merge(x,y);}else if(flag == 6){split(root,a,x,y);printf("%d\n",tr[kth(y,1)].v);root=merge(x,y);}}return 0;
}

练习题：

P3391 【模板】文艺平衡树. -> 翻转操作
P1503 鬼子进村. -> 哨兵节点

求点赞QWQ