fhq treap(无旋treap)
treap:其中每个点有输入值与随机值两种值,输入值满足二叉树性质,随机值满足堆性质。
而fhq如何实现平衡呢
它需要两个操作:分裂与合并
分裂:
目的:将其分成所有权值都大于或小于等于某一值的两棵平衡树
我们现在需要两个指针,每一次走到该点权值是否大于该值的反方向
点击查看代码
//pushup()一般是用来更改每一点的size...
void split(int &a,int &b,int p){
if(p==0){
a=b=0;
pushup(p);
return ;
}
if(e[p].sm<=val){//此处val为进行分离的那一个值
a=p;
split(e[p].r,b,e[p].r);
}
else{
b=p;
split(a,e[p].l,e[p].l);
}
pushup(p);
}