WBLT

$\rm Treap$ 足够优秀，但其缺憾有几点：

并不 $\rm Leafy$ ，合并需要合并三份而不是两份，在上面进行线段树操作更加繁琐，查询区间信息需要裂开合并，不能直接像线段树一样求。
如果对其进行可持久化，倘若新节点的随机权值直接复制原节点，那么我们无法进行“拼接两棵已有的平衡树”，一个节点自己拼接自己 $\log$ 次就足以让随机权值爆炸。
每次随机难以调试，不过这并不是大问题，调试时使用固定的随机种子即可。

解决第二个问题，目前主流的做法是抛弃随机权值，而是合并时按照 $\rm size$ 加权随机谁当根，这个做法目前处于无人会证且无人会卡的尴尬境地，所以可以放心使用。

另一个选择是学习 $\rm WBLT$ ，它的 $\rm Leafy$ 和自动支持可持久化是很有用的。

Leafy 化

将一棵树 $\rm Leafy$ 化，最大的不同就是原本一棵 $n$ 个节点的树现在需要 $2n-1$ 个节点来表示，所以节点的使用权不应在使用者手上，应该在数据结构的手中。

由于平衡树需要频繁地拆解、新建， $\text{Leafy Tree}$ 通常需要垃圾回收以减小空间常数。

这就很自然地引出了 new_node,uni,del 三个函数。

int new_node() {
    return t?s[t--]:++snt;
}
int uni(int x,int y) {
    int d=new_node();
    l(d)=x;r(d)=y;up(d);
    return d;
}
pair<int,int> del(int x) {
    s[++t]=x;down(x);
    return {l(x),r(x)};
}

WBLT 的平衡策略 & 分裂合并实现

$\rm WBLT$ 有一个平衡常数 $\alpha$ ，每个非叶子节点都要保证 $\min(siz(ls(x)),siz(rs(x)))\ge \alpha siz(x)$ ，对于常见的写法， $\alpha$ 大约在 $[0.1818,0.2929]$ 之间时，可以保证理论复杂度，通常取 $0.25$ 常数小，此时可以用位运算优化乘法。

非旋平衡树因为理念简单广受好评，此处我们也采用非旋写法。

$\rm WBLT$ 唯一重要的是其 $\rm merge$ ，即左右拼接两棵树的过程，其余部分都并不涉及平衡策略的应用。

根据集训队论文的合并方式：在合并两棵树 $x,y$ 时，若直接拼接满足平衡策略，则直接拼接。

否则我们找到更小的那棵，假设是 $x$ ：

若 $x+l(y)$ 与 $r(y)$ 满足平衡策略，则递归 uni(mer(x,l(y)),r(y))。
否则， $x,r(y)$ 都很小， $l(y)$ 很大，我们递归 mer(mer(x,l(l(y))),mer(r(l(y)),r(y)))。

不会证复杂度。

分裂是简单的，我们仿照非旋 $\rm Treap$ ，把裂开的几棵树向答案调用合并即可。

int mer(int x,int y) {
    if(!x||!y) return x|y;
    int k=siz[x]+siz[y]>>2;
    if(siz[x]<k) {
        auto[l,r]=del(y);
        if(siz[r]>=k) return uni(mer(x,l),r);
        auto[u,v]=del(l);
        return mer(mer(x,u),mer(v,r));
    } else if(siz[y]<k) {
        auto[l,r]=del(x);
        if(siz[l]>=k) return uni(l,mer(r,y));
        auto[u,v]=del(r);
        return mer(mer(l,u),mer(v,y));
    } else return uni(x,y);
}
void spl(int x,int k,int &l,int &r) {
    if(!x) return void(l=r=0);
    if(siz[x]<=k) return void((l=x,r=0));
    if(!k) return void((l=0,r=x));
    auto[u,v]=del(x);
    if(siz[u]>=k) spl(u,k,l,r),r=mer(r,v);
    else spl(v,k-siz[u],l,r),l=mer(u,l);
}

有了分裂合并，就自然地会插入删除二分等等操作了。

参考资料

IOI2018 集训队论文：Leafy Tree 及其实现的加权平衡树。