文章目录
前言基本操作合并操作分离操作【扩展】分离操作
应用操作插入其他操作
结束语关于本文作者鸣谢
前言
去年底我学了Treap,Splay和替罪羊。综合起来看，我个人认为还是FHQ_Treap比较实用。重点是比较好写而且写起来不容易挂。对于我这种蒟蒻，在写Treap和Splay时是常常爆炸的。所以FHQ_Treap成了蒟蒻我写平衡树的唯一救命稻草。
记得当时我没怎么学FHQ_Treap,今天我就来复习一下这个神奇的数据结构。
基本操作
这个玩意儿基本操作很少，但是能完成所有的平衡树操作
合并操作
int merge(int x
, int y
) {
if(!x
||!y
) return x
+y
;
if(rd
[x
]<rd
[y
]) {
ch
[x
][1]=merge(ch
[x
][1], y
);
up_node(x
);
return x
;
} else {
ch
[x
][0]=merge(x
, ch
[y
][0]);
up_node(y
);
return y
;
}
}
分离操作
void split(int now
, int p
, int &x
, int &y
) {
if(!now
) x
=y
=0;
else {
if(val
[now
]<=k
) {
x
=now
, split(ch
[now
][1], k
, ch
[now
][1], y
);
} else {
y
=now
, split(ch
[now
][0], k
, x
, ch
[now
][0]);
}
up_node(now
);
}
}
【扩展】分离操作
摘自这里，侵删
应用操作
插入
int insert(int &root
, int x
) {
int a
, b
;
int v
=val
[x
];
split(root
, v
, a
, b
);
root
=marge(marge(a
, x
), b
);
}
其他操作
void insert(int v
) {
int x
,y
;
split(rt
,x
,y
,v
-1);
merge(x
,x
,newnode(v
));
merge(rt
,x
,y
);
}
void del(int v
) {
int x
,y
,z
;
split(rt
,x
,y
,v
);
split(x
,x
,z
,v
-1);
merge(z
,ls
[z
],rs
[z
]);
merge(x
,x
,z
);
merge(rt
,x
,y
);
}
void rk(int v
) {
int x
,y
;
split(rt
,x
,y
,v
-1);
printf("%d\n",sz
[x
]+1);
merge(rt
,x
,y
);
}
int kth(int k
) {
int x
=rt
;
while(1) {
if(k
==sz
[ls
[x
]]+1)return val
[x
];
if(k
<=sz
[ls
[x
]])x
=ls
[x
];
else k
-=sz
[ls
[x
]]+1,x
=rs
[x
];
}
}
void pre(int v
) {
int x
,y
;
split(rt
,x
,y
,v
-1);
printf("%d\n",sz
[x
]?kth(x
,sz
[x
]):-inf
);
merge(rt
,x
,y
);
}
void suf(int v
) {
int x
,y
;
split(rt
,x
,y
,v
);
printf("%d\n",sz
[y
]?kth(y
,1):inf
);
merge(rt
,x
,y
);
}
这些都不是很难，不需要注释
结束语
如果你不理解，最好是自己打一遍代码或者是做一个有关FHQ_Treap的梦，就什么都懂了。
关于本文
作者
海洋，初一大蒟蒻
鸣谢
巨学博客
