更好写的平衡树：FHQ-Treap

complete_binary_tree · 2025-08-29 17:18:47 · 个人记录

什么是 FHQ-Treap？

FHQ-Treap 是一种无旋 Treap。它由于无旋所以可以支持区间操作和可持久化。而且它非常好写。

:::info[什么是 Treap]

Treap = Tree + Heap，顾名思义它是树和堆的组合体：每一个节点以及其的子树都满足堆的性质的一种二叉树。

显然它是二叉搜索树。

有旋 Treap 请出门左转 OI-Wiki。

:::

FHQ-Treap 的思想是？

FHQ-Treap 的核心思想是 分裂(split) 和 合并(merge)。

分裂时，会给定一个参数 x，把树分为两个部分，左边 \leq x，右边 > x。

:::info[如何实现？] 考虑分裂每个节点时，它要么放在左子树的最右点，要么放在右子树的最左点。

• 当它的值 \leq x 时，那么它和它的左子树一定能放在左子树的最右点下，所以只要考虑右子树即可；

• 否则它和它的右子树一定能放在右子树的最左点下，只需考虑左子树即可。

它的时间复杂度是 O(h) 的，其中 h 是树高。

参考实现：

/*
split(
  [in] x 当前要划分的节点
  [in] val 把节点分为 <=val 和 >val 两部分
  [out] x1 左子树的最右点
  [out] x2 右子树的最左点
) -> void
*/
void split(int x,int val,int&x1,int&x2){
    if(!x){ //空
        x1=x2=0; //赋值0
        return;
    }
    pushdown(x);
    if(t[x].val<=val){
        x1=x; //分到左子树的最右点
        split(t[x].rt,val,t[x].rt,x2); //考虑右子树
    }
    else{
        x2=x; //分到右子树的最左点
        split(t[x].lt,val,x1,t[x].lt); //考虑左子树
    }
    update(x);
}

:::

合并时，需要接受两个子树的根节点，需要保证前子树的所有值都小于等于后子树的最小值。合并时需要按照随机数决定哪个节点在上来保证高度。

:::info[如何实现？] 如果前子树的根的随机值较小，则让前子树的根在上；否则让后子树的根在上。

时间复杂度 O(h)。可以证明，合并出来的树高 h 是 \log n 级别的。

参考实现：

/*
merge(
  [in] x1 前子树
  [in] x2 后子树
) -> int 合并后子树根
*/
int merge(int x1,int x2){
    if(!x1||!x2)return x1|x2; //有一个为空，返回另一个
    pushdown(x1),pushdown(x2);
    if(t[x1].rnd<t[x2].rnd){ //前子树根随机数小
        t[x1].rt=merge(t[x1].rt,x2); //前子树根的右子树与后子树合并
        update(x1);
        return x1;
    }
    t[x2].lt=merge(x1,t[x2].lt); //后子树根的左子树与前子树合并
    update(x2);
    return x2;
}

:::

如何使用 FHQ-Treap 实现一般平衡树的操作？

以 【模板】普通平衡树（数据加强版） 为例：

• 插入 x：按 x split 成两棵子树，然后把 x 放中间，依次合并即可。

• 删除 x：按 x split 成两棵子树，然后把左子树按 x-1 split 成两棵子树，这样就得到 <x,=x,>x 三棵子树。删除 =x 子树的根节点（就是合并左右儿子）然后依次合并即可。

• 查询 x 的 rank：维护子树 size，查询时 split 出 <x 的子树，查询根节点 size 即可。

• 查询 rank x：维护 size，像普通二叉搜索树往下搜即可。

• 查询 x 的前驱：分裂出 <x 的子树，查询最大值。

• 查询 x 的后继：分裂出 >x 的子树，查询最小值。

核心代码：

const int N=2e6+5;
mt19937 rd(time(0));
int tot=0;
struct tree{int lt,rt,val,rnd,siz;}t[N]; //结构体
inline int create(int val){ //新建节点
    int x=++tot;
    t[x].rnd=rd();
    t[x].val=val;
    t[x].siz=1;
    return x;
}
inline void update(int x){t[x].siz=t[t[x].lt].siz+t[t[x].rt].siz+1;} //上传
void split(int x,int val,int&lprt,int&rplt){ //分裂
    if(!x){
        lprt=rplt=0;
        return;
    }
    if(t[x].val<=val){
        lprt=x;
        split(t[x].rt,val,t[x].rt,rplt);
    }
    else{
        rplt=x;
        split(t[x].lt,val,lprt,t[x].lt);
    }
    update(x);
}
int merge(int x1,int x2){ //合并
    if(!x1||!x2)return x1+x2;
    if(t[x1].rnd<t[x2].rnd){
        t[x1].rt=merge(t[x1].rt,x2);
        update(x1);
        return x1;
    }
    t[x2].lt=merge(x1,t[x2].lt);
    update(x2);
    return x2;
}
int rt=0;
inline int val(int rt,int rk){ //查询 rk val
    int x=rt;
    while(1){
        if(!x)return -1;
        if(t[t[x].lt].siz>=rk)x=t[x].lt;
        else if(t[t[x].lt].siz+1==rk)return t[x].val;
        else rk-=t[t[x].lt].siz+1,x=t[x].rt;
    }
    return -1;
}
inline void insert(int x){ //插入
    int lt,rt,nn=create(x);
    split(::rt,x,lt,rt);
    lt=merge(lt,nn);
    ::rt=merge(lt,rt);
}
inline void del(int x){ //删除
    int llt,lrt,lt,rt;
    split(::rt,x,lt,rt);
    split(lt,x-1,llt,lrt);
    lrt=merge(t[lrt].lt,t[lrt].rt);
    lt=merge(llt,lrt);
    ::rt=merge(lt,rt);
}
inline int getrk(int x){ //x排名
    int lt,rt;
    split(::rt,x-1,lt,rt);
    int siz=t[lt].siz;
    ::rt=merge(lt,rt);
    return siz;
}
inline int getp(int x){ //前驱
    int lt,rt;
    split(::rt,x-1,lt,rt);
    int p=val(lt,t[lt].siz);
    ::rt=merge(lt,rt);
    return p;
}
inline int gets(int x){ //后继
    int lt,rt;
    split(::rt,x,lt,rt);
    int s=val(rt,1);
    ::rt=merge(lt,rt);
    return s;
}

如何使用 FHQ-Treap 实现区间操作？

很简单，把区间 split 出来，然后给根节点操作即可。

例如 P3372 【模板】线段树 1，可以 split 出来以后直接给根节点打懒标记、更新 sum 和根节点的值。提交记录