fhq-Treap 合并的技巧

我们使用现场随机：

设 \(x,y\) 为两棵树的根，我们以 \(\dfrac{siz(x)}{siz(x)+siz(y)}\) 的概率将 \(y\) 合并到 \(x\) 上，否则将 \(x\) 合并到 \(y\) 上。

代码

1
2
3
4
5
6
7
8
int mrg(int x, int y)
{
    if (!x || !y) return x + y;
    if (Rand(1, siz[x] + siz[y]) <= siz[x])
        return c[x][1] = mrg(c[x][1], y), psu(x), x;
    else
        return c[y][0] = mrg(x, c[y][0]), psu(y), y;
}

这样可以保证按普通二叉搜索树建树的复杂度和可持久化平衡树复制节点的复杂度正确。