浅析 FHQ-Treap&Treap

ingo_dtw · 2026-01-09 23:02:00 · 算法·理论

前言

会做模板题我们只知道在平衡树上加一个值和查询平衡树上某个元素排名第几，排名第几的元素是什么，在实际使用过程中你发现这些功能并不是很常用。

这个时候，我们需要维护的不再是元素本身的值，而是一个序列，也就是说我们插入不再是使用一个元素的值作为插到哪的根据，而是使用元素的下标。此外，我们还需要注意我门进行分裂/合并的时候也不是使用元素的值而是下标。

P4036 [JSOI2008] 火星人

题意很简单，求一段后缀与一段后缀的 LCQ 不难注意到，如果没有修改操作，我们完全可以对原字符串 hash 然后使用二分求出，但是这里需要插入和修改操作，使得我们需要使用平衡树 n\log^2n 解决。 :::success[Ac Code]

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long 
#define ull unsigned long long
#define R register
#define rint register int
#define _ read()
inline bool blank(const char &x)
{
    return !(x^13)||!(x^32)||!(x^10)||!(x^9);
}
inline int read()
{
    rint r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
const int N=5e5+10,B=131;
ull b[N];
char c[N];
mt19937 rnd(1);
struct FHQ_Treap
{
    int root=0,cnt=0,len=0;ull cc[N];
    struct node
    {
        int l,r,s,siz;ull h;
    }tr[N];
    inline int neo(char x)
    {
        tr[++cnt]={0,0,(int)(rnd()),1,(ull)(x)};
        cc[cnt]=x;
        return cnt;
    }
    inline void pushup(rint u)
    {
        if(!u) return;
        tr[u].siz=tr[tr[u].l].siz+tr[tr[u].r].siz+1;
        tr[u].h=tr[tr[u].l].h*b[tr[tr[u].r].siz+1] + b[tr[tr[u].r].siz]*cc[u] + tr[tr[u].r].h;
    }
    inline pair<int,int> split(rint u,rint k)
    {
        if(!u) return {0,0};
        if(tr[tr[u].l].siz+1<=k)
        {
            auto x=split(tr[u].r,k-(tr[tr[u].l].siz+1));
            tr[u].r=x.first;
            pushup(u);            
            return {u,x.second};
        }
        else
        {
            auto x=split(tr[u].l,k);
            tr[u].l=x.second;
            pushup(u);
            return {x.first,u};
        }
    }
    inline int merge(rint l,rint r)
    {
        if(!l||!r) return l|r;
        if(tr[l].s<tr[r].s)
        {
            tr[l].r=merge(tr[l].r,r);
            pushup(l);
            return l;
        }
        else
        {
            tr[r].l=merge(l,tr[r].l);
            pushup(r);
            return r;
        }
    }
    inline void insert(rint p,char x)
    {
        auto [l,r]=split(root,p);++len;
        root=merge(merge(l,neo(x)),r);
    }
    inline void modify(rint p,char x)
    {
        auto [l,r]=split(root,p-1);
        auto [mid,rr]=split(r,1);
        tr[mid].h=cc[mid]=x;
        root=merge(merge(l,mid),rr);
    }
    inline ull query(rint ql,rint qr)
    {
        if(ql>qr) return 0;
        auto [l,midr]=split(root,ql-1);
        auto [mid,r]=split(midr,qr-ql+1);
        ull ans=tr[mid].h;
        root=merge(merge(l,mid),r);
        return ans;
    }

}tr;
signed main() 
{  
    memset(tr.tr,0,sizeof(tr.tr));
    scanf("%s",c+1);
    b[0]=1;
    for(rint i=1;i<N;++i) b[i]=b[i-1]*B;
    for(rint i=1;c[i];++i)
    {
        tr.insert(i-1,c[i]);

    }
    ull p=0;    
    // auto [lp,midr]=tr.split(tr.root,3-1);
    // cout<<midr<<' ';
    // auto [mid,rp]=tr.split(midr,1);
    // cout<<mid<<' ';
    // cout<<tr.tr[mid].h<<endl;
    // for(rint i=3;c[i];++i) cout<<tr.query(i,i)<<endl;
    // cout<<endl;
    rint q=_;
    while(q--)
    {
        char op;read(op);
        if(op=='Q')
        {
            rint x=_,y=_;
            rint l=0,r=tr.len-max(x,y)+1,mid,ans=0;
            while(l<=r)
            {
                mid=l+r>>1;
                if(tr.query(x,x+mid-1)==tr.query(y,y+mid-1)) ans=mid,l=mid+1;
                else r=mid-1;
            }
            out(ans);pc('\n');
        }
        else if(op=='R')
        {
            rint x=_;char y;read(y);
            tr.modify(x,y);
        }
        else
        {
            rint x=_;char y;read(y);tr.insert(x,y);
        }
    }
    return 0; 
} 
//我也要写吗

:::

P3391 【模板】文艺平衡树

考虑每次翻转的时候把需要翻转的区间切出来，然后对于这个节点打上类似于线段树的懒标记，每次分裂/合并前下传即可。 :::success[Ac Code]

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long 
#define ull unsigned long long
#define R register
#define rint register int
#define _ read()
inline bool blank(const char &x)
{
    return !(x^13)||!(x^32)||!(x^10)||!(x^9);
}
inline int read()
{
    rint r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
const int N=1e5+10;
mt19937 rnd(time(0));
struct FHQ_Treap
{
    int root,cnt;
    struct node
    {
        int l,r,s,x,siz;bool set;
    }tr[N];
    inline int neo(rint v)
    {
        tr[++cnt]={0,0,(int)(rnd()),v,1,0};
        return cnt;
    }
    inline void pushup(rint u)
    {
        tr[u].siz=tr[tr[u].l].siz+1+tr[tr[u].r].siz;
    }
    inline void pushdown(rint u)
    {
        if(tr[u].set)
        {
            swap(tr[u].l,tr[u].r);
            if(tr[u].l) tr[tr[u].l].set^=1;
            if(tr[u].r) tr[tr[u].r].set^=1;
            tr[u].set=0;
        }
    }
    inline pair<int,int>split(rint u,rint k)
    {
        if(!u) return {0,0};
        pushdown(u);
        if(tr[tr[u].l].siz+1<=k)
        {
            auto x=split(tr[u].r,k-(tr[tr[u].l].siz+1));
            tr[u].r=x.first;
            pushup(u);
            return {u,x.second};
        }
        else
        {  
            auto x=split(tr[u].l,k);
            tr[u].l=x.second;
            pushup(u);
            return {x.first,u};
        }
    }
    inline int merge(rint l,rint r)
    {
        if(!l||!r) return l|r;
        if(tr[l].s<tr[r].s)
        {
            pushdown(l);
            tr[l].r=merge(tr[l].r,r);
            pushup(l);
            return l;
        }
        else
        {
            pushdown(r);
            tr[r].l=merge(l,tr[r].l);
            pushup(r);
            return r;
        }
    }
    inline void insert(rint v)
    {
        root=merge(root,neo(v));
    }
    inline void modify(rint ql,rint qr)
    {
        auto [l,midr]=split(root,ql-1);
        auto [mid,r]=split(midr,qr-ql+1);
        tr[mid].set^=1;
        root=merge(merge(l,mid),r);
    }
    inline int query(rint k)
    {
        auto [l,rmid]=split(root,k-1);
        auto [mid,r]=split(rmid,1);
        rint ans=tr[mid].x;
        root=merge(merge(l,mid),r);
        return ans;
    }
}tr;
signed main() 
{  
    rint n=_,q=_;
    for(rint i=1;i<=n;++i) tr.insert(i);
    while(q--)
    {
        rint l=_,r=_;tr.modify(l,r);
    }
    for(rint i=1;i<=n;++i)
    {
        out(tr.query(i));pc(' ');
    }
    return 0; 
} 
//我也要写吗

:::

带旋 \texttt{Treap}

首先，带旋 \texttt{Treap} 最大的特点就是左旋右旋。

左旋

如上图，现在我们把 B 左旋，这个时候 D 就成为根结点，然后 B 要成为 D 的左子树，但是和 E 冲突，因为是 BST 所以 B 肯定小于 E 所以把 E 接到 B 的右子树。

来看看改变了什么，首先根（B）的右子树（D）变为其右子树（D）的左子树（E），其次根（B）的右子树（D）的左子树变为根（B）。

:::success[Code]

inline int zag(rint u)
{
    rint v=tr[u].r;
    tr[u].r=tr[v].l;
    tr[v].l=u;
    pushup(u);
    pushup(v);
    return v;
}

:::

右旋

如上图，我们先不管具体的值，只看大小关系，我们需要将它从 F 那里右旋，将 F 往下调，于是 B 变为根节点，但是你发现 F>B 所以 F 变为 B 的右节点，可是 B 已经有个右节点 E 了，怎么办呢？注意到已 B 为根的子树全都小于 F 所以 E 应该在 F 的左子树。

如上图，现在右旋完了，我们对比一下看一下改变了啥，首先就是 B 的右子树变为以 F 为根的子树，F 的左子树从 B 变为 B 的右子树。

:::success[Code]

inline int zig(rint u)
{
    rint v=tr[u].l;
    tr[u].l=tr[v].r;
    tr[v].r=u;
    pushup(u);
    pushup(v);
    return v;
}

:::

插入

首先，我们要保证 BST 性质不被破坏，那么我们就按照 BST 性质，找到一个空节点建立这个新插入的点，然后如果破坏了小根堆性质，那么就左旋或者右旋调整过来。

:::success[Code]

inline int insert(rint u,rint x)//当前的点为u，插入值为x的点
{
    if(!u) return neo(x);
    if(x==tr[u].x) tr[u].cnt++;//相等
    else if(x<tr[u].x)
    {
        tr[u].l=insert(tr[u].l,x);
        if(tr[tr[u].l].s>tr[u].s) u=zig(u);//左儿子优先级高，右旋
    }
    else
    {
        tr[u].r=insert(tr[u].r,x);
        if(tr[u].s>tr[tr[u].r].s) u=zag(u);//右儿子优先级高，左旋
    }
    pushup(u);
    return u;
}

:::

删除

这个很有意思，首先我们先根据 BST 的性质，找到这节点，我们分类讨论一下：

• 如果这个节点不止一个：
  • 删掉就好。
• 如果只有一个：
  • 如果是叶子节点：
  • 删掉就好。
  • 如果是有一个左节点：
  • 将要删掉的节点左旋，然后就变成叶子节点，删掉就好。
  • 如果是有一个右节点：
  • 将要删掉的节点右旋，然后就变成叶子节点，删掉就好。
  • 如果两个节点都有：
  • 比较两个节点的优先级，优先级低的左旋或者右旋上去，然后要删掉的节点变成叶子节点，删掉就好。

:::success[Code]

inline int erase(rint u,rint x)
{
    if(!u) return 0;//没这个节点
    if(x<tr[u].x)//在左子树
    {
        tr[u].l=erase(tr[u].l,x);
    }
    else if(x>tr[u].x)//在右子树
    {
        tr[u].r=erase(tr[u].r,x);
    }
    else//就是这个节点
    {
        if(tr[u].cnt>1) tr[u].cnt--;//大于一个
        else
        {
            if(!tr[u].l&&!tr[u].r) return 0;//删掉
            else if(tr[u].l&&!tr[u].r)
            {
                u=zig(u);tr[u].r=erase(tr[u].r,x);//删除，注意到这里不是叶子节点还要继续右旋到叶子节点
            }
            else if(!tr[u].l&&tr[u].r)
            {
                u=zag(u);tr[u].l=erase(tr[u].l,x);//同理
            }
            else 
            {
                if(tr[tr[u].l].s<tr[tr[u].r].s)//左边的小，右旋
                {
                    u=zig(u);tr[u].r=erase(tr[u].r,x);
                }
                else
                {
                    u=zag(u);tr[u].l=erase(tr[u].l,x);
                }                
            }
        }
    }
    pushup(u);
    return u;
}

:::

查询排名

怎么查询 x 的排名呢？还是按照 BST 的性质找 x。

• 找到了：
  • 返回之前和加上左子树的大小加上 1。
• 如果在左子树：
  • 继续找。
• 如果在右子树：
  • 加上左子树和这个节点本身的大小继续找。

:::success[Code]

inline int find1(rint u,rint x)
{
    if(!u) return 1;//没有x这个节点，排名1
    if(x==tr[u].x)
    {
        return tr[tr[u].l].siz+1;//左子树大小加1
    }
    else if(x<tr[u].x)
    {
        return find1(tr[u].l,x);
    }
    else
    {
        return tr[tr[u].l].siz+tr[u].cnt+find1(tr[u].r,x);
    }
}

:::

查询第 k 小

怎么查询第 k 小的数呢？和 \texttt{FHQ-Treap} 有点像，不过我们这次用递归来找。

:::success[Code]

inline int find2(rint u,rint k)
{
    if(!u) return -114514;//没有这个排名
    if(k<=tr[tr[u].l].siz)//在左子树中
    {
        return find2(tr[u].l,k);
    }
    else if(k<=tr[tr[u].l].siz+tr[u].cnt)//就是这个节点
    {
        return tr[u].x;
    }
    else//在右子树
    {
        return find2(tr[u].r,k-tr[tr[u].l].siz-tr[u].cnt);
    }
}

:::

查询前驱

怎么查询 x 的前驱？我们来分情况讨论一下：

• 如果当前节点的值大于等于 x：
  • 说明 x 的前驱在左子树。
• 否则，查询先查询右子树有没有比 x 小点的，最后和当前节点取 \max。

:::success[Code]

inline int pre(rint u,rint x)//查询 x 前驱
{
    if(!u) return -1145141919810;//这个子树中没有 x 前驱
    if(x<=tr[u].x) return pre(tr[u].l,x);//前驱不是右子树和当前节点
    return max(tr[u].x,pre(tr[u].r,x));
}

:::

查询后继

怎么查询 x 的后继呢？来讨论一下：

• 如果当前节点小于等于 x：
  • 后继肯定不在左子树或者当前节点，去右子树看看。
• 如果当前节点大于 x：
  • 去左子树看看大于 x 的，和当前节点取 \min。

:::success[Code]

inline int nxt(rint u,rint x)//查询x后继
{
    if(!u) return 1145141919810;//这个子树没有 x 后继
    if(tr[u].x<=x) return nxt(tr[u].r,x);
    return min(tr[u].x,nxt(tr[u].l,x)); 
}

:::

完整代码

:::success[Ac Code]

#include <bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define R register
#define int long long
#define rint register int
#define _ read<int>()
inline bool blank(R const char &x){return !(x^32)||!(x^10)||!(x^13)||!(x^9);}
template<class T>inline T read()
{
    R T r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(R char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
const int N=1e5+10;
mt19937 rnd(time(0)*114514/1919810);
int root=0;
struct Treap
{
    struct Tree{int l,r,siz,cnt,x,s;}tr[N];
    int cnt;
    inline int neo(rint x)
    {
        tr[++cnt]={0,0,1,1,x,(int)rnd()};
        return cnt;
    }
    inline void pushup(rint u){tr[u].siz=tr[tr[u].l].siz+tr[tr[u].r].siz+tr[u].cnt;}
    inline int zag(rint u)//左旋
    {
        rint v=tr[u].r;
        tr[u].r=tr[v].l;
        tr[v].l=u;
        pushup(u);pushup(v);
        return v;
    }
    inline int zig(rint u)//右旋
    {
        rint v=tr[u].l;
        tr[u].l=tr[v].r;
        tr[v].r=u;
        pushup(u);pushup(v);
        return v;
    }
    inline int insert(rint u,rint x)//当前的点为u，插入值为x的点
    {
        if(!u) return neo(x);
        if(x==tr[u].x) tr[u].cnt++;//相等
        else if(x<tr[u].x)
        {
            tr[u].l=insert(tr[u].l,x);
            if(tr[tr[u].l].s>tr[u].s) u=zig(u);//左儿子优先级高
        }
        else
        {
            tr[u].r=insert(tr[u].r,x);
            if(tr[u].s>tr[tr[u].r].s) u=zag(u);//右儿子优先级第
        }
        pushup(u);
        return u;
    }
    inline int erase(rint u,rint x)
    {
        if(!u) return 0;//没这个节点
        if(x<tr[u].x)//在左子树
        {
            tr[u].l=erase(tr[u].l,x);
        }
        else if(x>tr[u].x)//在右子树
        {
            tr[u].r=erase(tr[u].r,x);
        }
        else//就是这个节点
        {
            if(tr[u].cnt>1) tr[u].cnt--;//大于一个
            else
            {
                if(!tr[u].l&&!tr[u].r) return 0;//删掉
                else if(tr[u].l&&!tr[u].r)
                {
                    u=zig(u);tr[u].r=erase(tr[u].r,x);//删除，注意到这里不是叶子节点还要继续右旋旋到叶子节点
                }
                else if(!tr[u].l&&tr[u].r)
                {
                    u=zag(u);tr[u].l=erase(tr[u].l,x);//同理
                }
                else 
                {
                    if(tr[tr[u].l].s<tr[tr[u].r].s)//左边的小，右旋
                    {
                        u=zig(u);tr[u].r=erase(tr[u].r,x);
                    }
                    else
                    {
                        u=zag(u);tr[u].l=erase(tr[u].l,x);
                    }                
                }
            }
        }
        pushup(u);
        return u;   
    }
    inline int find1(rint u,rint x)
    {
        if(!u) return 1;//没有x这个节点，排名1
        if(x==tr[u].x)
        {
            return tr[tr[u].l].siz+1;//左子树大小加1
        }
        else if(x<tr[u].x)
        {
            return find1(tr[u].l,x);
        }
        else
        {
            return tr[tr[u].l].siz+tr[u].cnt+find1(tr[u].r,x);
        }
    }
    inline int find2(rint u,rint k)
    {
        if(!u) return -114514;//没有这个排名
        if(k<=tr[tr[u].l].siz)//在左子树中
        {
            return find2(tr[u].l,k);
        }
        else if(k<=tr[tr[u].l].siz+tr[u].cnt)//就是这个节点
        {
            return tr[u].x;
        }
        else//在右子树
        {
            return find2(tr[u].r,k-tr[tr[u].l].siz-tr[u].cnt);
        }
    }
    inline int pre(rint u,rint x)//查询 x 前驱
    {
        if(!u) return -1145141919810;//这个子树中没有 x 前驱
        if(tr[u].x>=x) return pre(tr[u].l,x);//前驱不是右子树和当前节点
        return max(tr[u].x,pre(tr[u].r,x));
    }
    inline int nxt(rint u,rint x)//查询x后继
    {
        if(!u) return 1145141919810;//这个子树没有 x 后继
        if(tr[u].x<=x) return nxt(tr[u].r,x);
        return min(tr[u].x,nxt(tr[u].l,x)); 
    }
}tr;

signed main()
{  
    rint q=_;
    while(q--)
    {
        rint op=_,x=_;
        if(op==1)
        {
            root=tr.insert(root,x);
        }
        else if(op==2)
        {
            root=tr.erase(root,x);
        }
        else if(op==3)
        {
            out(tr.find1(root,x));pc('\n');
        }
        else if(op==4)
        {
            out(tr.find2(root,x));pc('\n');
        }
        else if(op==5)
        {
            out(tr.pre(root,x));pc('\n');
        }
        else 
        {
            out(tr.nxt(root,x));pc('\n');
        }
    }
    return 0;
}

:::

总结

个人认为这两种 \texttt{Treap} 各有各的优点，\texttt{FHQ-Treap} 简单易上手，可持久化、区间操作比较简单，带旋 \texttt{Treap} 左旋右旋个人感觉比较难理解，不过它常数比 \texttt{FHQ-Treap} 小（也许是我写法的问题），实际解决问题中，还是按需选择吧。

upd

2026/2/8：感谢 @JasmineCloud__ 指出的错误，已修正。

2026/3/28： 增加了文艺平衡树部分，并修改了一些错误。

欢迎各位指出我的错误！