$\LARGE{引入}$
$\textrm{fhq-treap}$ 是一种不支持旋转的 $\textrm{treap}$ ,由范浩强发明。
$\textrm{treap}$ 就是指 $\textrm{tree} + \textrm{heap}$ ,即二叉搜索树 $+$ 堆。
$\LARGE{概念}$
$\textrm{fhq-treap}$ 对于每一个点维护两个值, $key$ 和 $val$ ,$key$ 为树上排序的指标,$val$ 为一个随机值,保证 $\textrm{fhq-treap}$ 的时间复杂度。
对于 $key$ ,满足二叉搜索树性质,即对于每一个点 $x$ ,其左子树中 $key$ 小于它,右子树中 $key$ 大于它。
对于 $val$ ,满足小根堆性质,即对于每一个节点,它永远是以它为根的子树中 $val$ 值最小的。
$\LARGE{基本操作}$
$\textrm{fhq-treap}$ 有两个基本操作 : $\textrm{split}$ 和 $\textrm{merge}$ 。
$\large{\textrm{split}}$
$split$ 的功能是将一个树按 $key$ 值小于等于 $k$ 和大于 $k$ 划分成两棵树。
具体步骤是先判断根节点属于哪一棵树,若小于等于 $k$ ,则继续分割其右子树,否则分割左子树。
void split(int x, int k, int &l, int &r) { //l,r用于获取分割后两棵树的根节点
if (!x) {
l = 0, r = 0;
return;
} else if (tr[x].key <= k) { //属于左树
l = x;
split(tr[x].s[1], k, tr[x].s[1], r);
pushup(x);
} else { //属于右树
r = x;
split(tr[x].s[0], k, l, tr[x].s[0]);
pushup(x);
}
}
$\large{\textrm{merge}}$
$merge$ 操作是将两颗树按照 $val$ 合并起来,但操作前提是 $l$ 中的 $key$ 必须小于 $r$ 中的所有 $key$ 。
操作步骤是先比较两树根节点的 $val$ ,较小者为根,
若 $l$ 为较小者,由于要维护 $key$ 的顺序,继续将 $l$ 的右子树和 $r$ 合并,左子树保留,
若 $r$ 为较小者,同理将 $r$ 的左子树和 $l$ 合并,右子树保留。
int merge(int x, int y) {
if (!x || !y) return x | y;
if (tr[x].val < tr[y].val) {
tr[x].s[1] = merge(tr[x].s[1], y);
pushup(x);
return x;
} else {
tr[y].s[0] = merge(x, tr[y].s[0]);
pushup(y);
return y;
}
}