BST 总结 ：
\(\mathtt{Ps:}\) 由于作者实力不够，写错的地方请海涵，可以提出，加以修改。
BST 二叉排序树，有 左子树所有点 \(<\) 根 \(<\) 右子树所有点。
Splay:
伸展树，也就是 Spaly ，可以通过伸展操作将 \(x\) 变成 \(y\) 的子结点，并不改变二叉排序树的性质，其中 \(y\) 为 \(x\) 的祖先。
考虑 \(1\) 次操作，也就是将 \(x\) 变成 \(f(x)\) 。
旋转操作：Rotate(x)
void Rotate(int x){
int fa=f[x],ffa=f[fa],m=Get(x),n=Get(fa);
Con(Son(x,m^1),fa,m);
Con(fa,x,m^1);
Con(x,ffa,n);
Update(fa);Update(x);
}
其中的 Con 为：
void Con(int x,int y,int z){
if(x){f[x]=y;}
if(y){Son(y,z)=x;}
}
其中的 Update 为：
void Update(int x){
if(x){
Siz(p)=1;
if(Son(x,0)){Siz(x)+=Siz(Son(x,0));}
if(Son(x,1)){Siz(x)+=Siz(Son(x,1));}
}
}
此时的 Update 不能省略，因为改变了树的形态。
伸展操作： Splay(x,y)
void Splay(int x,int goal){
while(f[x]!=goal){
int fa=f[x];
if(f[fa]!=goal){Rotate(Get(fa)==Get(x)?fa:x);}
Rotate(x);
}
if(!goal){rt=x;}
}
这里是用双旋实现的，不难发现，单次 Splay 复杂度为 \(O(\log n)\) 。
双旋和单旋的区别，就在于上述代码的第 4 行。
双旋，可以保证 BST 接近于完全二叉树，而单旋会变得十分混乱，复杂度不能保证。
注意如果 \(y=0\) ，即将 \(x\) 旋转到根节点，那么要更新 rt 。
插入 \(x\) ：根据 BST 的性质，从根节点往下新生成 1 个叶子节点
删除 \(x\) ：找到 \(x\) 对应的编号，将其旋转到根节点，把左子树接在 \(x\) 的后继上，然后删除 \(x\) 。
将 \(x-1\) 旋转到根节点， \(x+1\) 旋转到 \(x-1\) 的右子树，那么 \(x\) 就在 \(x-1\) 的左子树上。
\(x\) 的前驱 ：找到 Son(x,0) 一直递归 x=Son(x,1) 。
\(x\) 的后继：找到 Son(x,1) 一直递归 x=Son(x,0) 。
查找 \(x\) 的排名：根据 BST 的性质，从根节点递归。
当 x=Val(now) 则返回 now ;
当 x<Val(now) 递归右子树 ;
当 x>Val(now) 递归左子树 .
查找排名为 \(x\) 的数：与上述情况类似。
查找最接近 \(x\) 的大于 / 大于等于 / 小于等于 / 小于 \(x\) 的数：与上述情况类似。
Splay 还可以实现区间操作。
查找区间 \([l,r]\) ：将 \(l-1\) 旋转到根节点，\(r+1\) 旋转到 \(l-1\) 的左子树，那么 \([l,r]\) 就在 \(r+1\) 的左子树上。
\(\mathtt{Ps:}\) 防止 \(l-1,r+1\) 不合法，可以插入 Inf 和 -Inf 避免，然后特判。
建树：
要满足 BST 的性质，需根据题目条件而改变。
查找第 \(k\) 大，排名第 \(k\) 的数等与值相关的操作，都需要按照值排序。
题目的操作与序列有关，那么就要按照序列排序。
\(\mathtt{Ps:}\) 这里所说的序列排序是符合题目要求之后的序列。
Build 与线段树很相似，如用这种方法建树，就要按照某个顺序排序，值或者序列 。
int Build(int l,int r,int fa){
int mid=(l+r)>>1,now=++cnt;
f[now]=fa;Val(now)=d[mid];
Son(now,0)=Son(now,1)=0;
if(l<=mid-1){
Son(now,0)=Build(l,mid-1,now);
}
if(r>=mid+1){
Son(now,1)=Build(mid+1,r,now);
}
Update(now);
return now;
}
这里给出的是按照序列排序的代码。
若要实现按照值排序，就在开始按照值排序即可。
Insert 就是 BST 独有的，只需插入过程中，实现排序即可。
void Insert(int k){
if(!cnt){
cnt++;Siz(cnt)=Num(cnt)=1;Val(cnt)=k;
Son(cnt,0)=Son(cnt,1)=f[cnt]=0;
rt=cnt;
}
else{
int now=rt,fa=0;
while(1){
if(Val(now)==k){
Num(now)++;
Update(now);Update(fa);
Splay(now,0);
return;
}
fa=now;now=Son(now,k>Val(now));
if(!now){
cnt++;Siz(cnt)=Num(cnt)=1;Val(cnt)=k;
Son(cnt,0)=Son(cnt,1)=0;
Son(fa,k>Val(fa))=cnt;
f[cnt]=fa;
Splay(cnt,0);
return;
}
}
}
}
这里给出的是按照值排序的代码。
若要实现按照序列排序的代码，就只需要 now=Son(now,1) 即可。
\(\mathtt{Ps:}\) Insert 建树每次插入 1 个节点都要 Splay ，不然有可能变成 1 条链。
能 Splay，就 Splay 。
对于区间操作，跟线段树比较类似，也可以添加 Tag 标记。
其中 Splay 可能有些变化。
比如要实现区间加法：
void Splay(int x,int goal){
int len=0;
for(int i=x;i;i=f[i]){q[++len]=i;}
for(int i=len;i;--i){P_d(q[i]);}
while(f[x]!=goal){
int fa=f[x];
if(f[fa]!=goal){Rotate(Get(fa)==Get(x)?fa:x);}
Rotate(x);
}
if(!goal){rt=x;}
}
改变的是 2 ~ 4 行。
由于 Splay 会改变树的形态，那么就要敢在操作前把标记下传。
那为什么不 Update 呢？
因为此时 Update 没用。
Rotate 会改变树的形态，所以只有在 Rotate之后再 Update 才游泳，这一点需要自己判断。
如果不想判断，也可以哪哪都加上 Update Push_down ，只不过有时候常数会变得无比巨大。
对于不知道如何处理的操作，一般都可以将其旋转到根节点，就迎刃而解了。
如果有多个操作该怎么办？
可以分析它们之间的关系。
比如区间翻转与区间加法毫无关联，也就是互相不影响，先做哪个都可以。
比如区间加法与区间乘法，那么就可以假设先做加法，再做乘法，如何把不和法的乘法变成加法，反之，同理。
这里可以参考 [模板]线段树2 。
无旋 Treap:
分裂操作：Split(rt,k,x,y)
将 以 rt 为根的数按把小于等于 \(k\) 的分离给 \(x\) ，把大于 \(k\) 的分离给 \(y\) ，变成以 \(x,y\) 为根的两棵树。
\(\mathtt{Ps:}\) 代码不难理解，故没有解释。
void Split(int rt,int k,int &x,int &y){
if(!rt){x=y=0;return;}
else if(Val(rt)<=k){
x=rt;
Split(Son(rt,1),k,Son(rt,1),y);
}
else{
y=rt;
Split(Son(rt,0),k,x,Son(rt,0));
}
Update(rt);
}
这里的 Split是按照权值分裂，其中 Update 同 Splay 。
合并操作：Merge(x,y)
将以 \(x,y\) 为根的两棵树合并成 1 棵树，并返回根。
int Merge(int x,int y){
if(!x||!y){
return x+y;
}
else if(Rd(x)<Rd(y)){
Son(x,1)=Merge(Son(x,1),y);
Update(x);
return x;
}
else{
Son(y,0)=Merge(x,Son(y,0));
Update(y);
return y;
}
}
其中的 Rd(x) 为插入节点时给的随机数，保证 Treap 的平衡。
-
插入 \(k\) ：
Split(rt,k,x,y)rt=Merge(Merge(x,New(k)),y) -
删除 \(k\) :
Split(rt,k,x,z)`Split(rt,k-1,x,y)` rt=Merge(Merge(x,Merge(Son(y,0),Son(y,1))),y)
查找值的操作，跟 Splay 一模一样。
无旋 Treap 也可以实现区间操作，但没有 Splay 那么好用。
想要实现区间操作，就必须按照序列排序。
\([l,r]\) 的区间操作：Split(rt,l-1,x,y)
Split(rt,l-r+1,y,z)
其中以 \(y\) 为根的树便是区间 \([l,r]\) 。
这里的 Split 是按照 Siz 分裂，原理与权值分裂相同。
\(\mathtt{Ps:}\) 如果操作会改变树的形态，那么就要在其之前 Update 和 Push_down
Push_down 之后 Update 。