Treap

概念：Treap 同时满足键值的二叉搜索树性质与随机优先级的堆性质。随机优先级使树高在期望意义下保持对数级。

关键步骤

按键将树分成小于等于 x 与大于 x 两部分（split），再按优先级合并（merge）。插入和删除都可转化为 split 与 merge；可额外维护子树大小实现第 k 小。

int merge(int a,int b){
    if(!a||!b) return a?a:b;
    if(pri[a]<pri[b]){ ch[a][1]=merge(ch[a][1],b); pull(a); return a; }
    ch[b][0]=merge(a,ch[b][0]); pull(b); return b;
}
void split(int p,int key,int& a,int& b){
    if(!p) a=b=0;
    else if(val[p]<=key) a=p,split(ch[p][1],key,ch[p][1],b),pull(a);
    else b=p,split(ch[p][0],key,a,ch[p][0]),pull(b);
}

复杂度

在优先级独立随机时，split、merge、插入、删除和查询的期望时间均为 O(log n)，空间 O(n)。随机数质量影响树高。