FHQ-Treap学习笔记

wenmingge · 2025-07-16 12:07:55 · 算法·理论

0.引言

要懂得 FHQ-Treap（无旋 Treap），我们必须先懂 Treap 的原理。

要懂得 Treap，我们必须先懂平衡树。

要懂得平衡树，我们必须先懂 BST（二叉搜索树）。

1.BST

BST，二叉搜索树，首先得是一颗二叉树。

其次，这颗树还得满足一个节点比它的左儿子大，比右儿子小。

那么维护这棵树就很简单了，只需要递归模拟即可，而其复杂度即为 O(h)。

一颗示例 BST，其中插入顺序为 [114,5,514,1,500,501,7]（可能的一种）：

BST模板（洛谷P5076）

2.平衡树

但是，我们注意到如果顺序趋近于单调递增/递减，那么它的复杂度（树高）就会趋近于单次 O(n)。

一颗示例 O(n) 的 BST，其中插入顺序为 [1,2,3,4,5]：

明显的，这颗树最优高度是 \log{n} 的，而平衡树就是维护高度为 O(\log{n})（注意，常数可能大于 1，所以是带 O 的），从而使得每个操作都为 O(\log{n}) 的复杂度（因为 BST 操作最多会遍历树高度）。

常见的平衡树有：Splay、（有旋）Treap、FHQ-Treap、红黑树（set 和 map 内部使用的平衡树）、SBT（Size Balanced Tree，好像是理论上最快的平衡树 实际被红黑树暴打）、AVL 树、替罪羊树（需要特定的不平衡率保持常数，是弱平衡的，但是有时候其它平衡树不好保持平衡，而替罪羊树比较方便）、WBLT、B 树（看算导知道的，主要用于硬盘）。

3.替罪羊树

既然说到了平衡树，这里先引入一个比较简单的平衡树——替罪羊树。

先分析一下为什么普通 BST 能被卡：一颗子树比另外一颗大太多，顺序趋近于单调递增/递减就会让一颗子树几乎是空的而另一颗几乎包括所有节点。于是乎我们可以当一颗子树占它和它兄弟树大小之和的 \alpha（不平衡率，常数）时，就视为这棵树已经不平衡了（比它的兄弟大太多），重建它。

重建方法：先中序遍历这整颗树，得到原数组，再递归，选取中间节点为父亲，左右两部分为子树继续递归。可以证明这样构建树是完全平衡的，是 \log{n} 高度的。

然后对于其它操作与普通 BST 一样，只要在插入时看不平衡率有没有达到 \alpha 就行。

但是 \alpha 对复杂度至关重要，经测验一般设置为 0.7 或 0.75。

替罪羊树虽简单，但复杂度差点，而且一般难以拓展，请读者自行使用替罪羊树写出模板题，也可以自行了解替罪羊树的应用。

4.Treap

既然在趋近有序时时间复杂度差，那么我们就反其道而行之，尽可能让它无序。

可以想到随机打乱，这样就可以无序了，可以证明这样构建 BST 高度是期望 O(\log{n}) 的（虽然是期望，但实际也很快）。

但是随机打乱需要在知道所有的情况下，如何动态解决？就是 Treap 的思路。

我们使用开始的例子，在节点旁标注其插入顺序中的位置：

惊人的发现，父节点的插入顺序比儿子（可以扩大到所有子孙节点）先（也可以通过 BST 的模拟方式证明）！也就是说 BST 在插入顺序上是一个（小根）堆！

这也是 Treap 名字的由来，Treap=Tree+Heap。

那么我们就可以在插入时随机一个顺序（变量维护，下文中将顺序称为优先级），然后同时使用 BST 的模拟和堆的维护来维护 Treap。

5.FHQ-Treap

先膜拜 FHQ-Treap 的发明人 FHQ（范浩强）。

FHQ-Treap 并不需要晦涩难懂的旋转操作（而且天生适合序列操作），因为 Treap 是通过随机的性质本身来保持平衡的，和维护（注意，不是保持）平衡的操作无关。

FHQ-Treap 的基本操作只有两个，是分裂与分化合并。

分裂并不涉及优先级，仅仅是将一颗 Treap 分成 \le x 和 >x 的两部分，因为 BST 和堆的结构都是递归的，所以 Treap 的结构也是递归的，故分裂操作并不会影响平衡性。实现见下文，递归即可。

合并是分裂的逆操作，可以将两颗 Treap 合并成一颗 Treap，约定合并左树的根值小于右树，那么如果左数优先级大于右树，根据 Treap 性质，递归合并左树右儿子和右树，反之递归合并右树左儿子和左树。实现见下文。

其它操作：插入 x，分裂出 \le x 和 >x，新建值为 x 的节点（节点一定是 Treap），合并到左树中，再将左树与右树合并；删除 x，分裂出 \le x 和 >x，再从左树分裂出 \le x-1(<x) 和 >x-1(>x)\le x+1（即 =x）的，合并 <x 和 >x 的，把 =x 弃之不理即可；x 排名，分裂出 \le x-1(<x) 和 >x-1(\ge x) 的，左树大小加一即为排名；第 k 小，不用分裂或合并，和 BST 一样就行；前驱，分裂出 \le x-1(<x) 和 >x-1(\ge x) 的，左树使用第 k 小求出最大的即可；后继，分裂出 \le x 和 >x 的，右树使用第 k 小求出最小的即可。

6.应用

简单运用

洛谷 P3369&P6136

思路

平衡树板子，上文已阐述。

加强版与普通版并无差别，只需加个异或。

代码

这里为 FHQ-Treap 在普通版的代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt,root;
struct Node
{
    int ls,rs,key,pri,sz;
}t[1000005];
void build(int x)
{
    t[++cnt].sz=1;
    t[cnt].ls=t[cnt].rs=0;
    t[cnt].key=x;
    t[cnt].pri=rand()*rand();
}
void update(int u)
{
    t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+1;
}
void split(int u,int x,int& L,int& R)
{
    if(!u)
    {
        L=R=0;
        return ;
    }
    if(t[u].key<=x)
    {
        L=u;
        split(t[u].rs,x,t[u].rs,R);
    }
    else
    {
        R=u;
        split(t[u].ls,x,L,t[u].ls);
    }
    update(u);
}
int merge(int L,int R)
{
    if(L==0||R==0)return L+R;
    if(t[L].pri>t[R].pri)
    {
        t[L].rs=merge(t[L].rs,R);
        update(L);
        return L;
    }
    t[R].ls=merge(L,t[R].ls);
    update(R);
    return R;
}
void insert(int x)
{
    int L,R;
    split(root,x,L,R);
    build(x);
    int tmp=merge(L,cnt);
    root=merge(tmp,R);
}
void del(int x)
{
    int L,R,p;
    split(root,x,L,R);
    split(L,x-1,L,p);
    p=merge(t[p].ls,t[p].rs);
    root=merge(merge(L,p),R);
}
int rk(int x)
{
    int L,R;
    split(root,x-1,L,R);
    int tmp=t[L].sz+1;
    root=merge(L,R);
    return tmp;
}
int _kth(int u,int k)
{
    if(k==t[t[u].ls].sz+1)return u;
    if(k<=t[t[u].ls].sz)return _kth(t[u].ls,k);
    if(k>t[t[u].ls].sz)return _kth(t[u].rs,k-t[t[u].ls].sz-1);
}
int kth(int k){return t[_kth(root,k)].key;}
int pre(int x)
{
    int L,R;
    split(root,x-1,L,R);
    int tmp=t[_kth(L,t[L].sz)].key;
    root=merge(L,R);
    return tmp;
}
int suc(int x)
{
    int L,R;
    split(root,x,L,R);
    int tmp=t[_kth(R,1)].key;
    root=merge(L,R);
    return tmp;
}
int n,op,x;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    cin>>n;
    while(n--)
    {
        cin>>op>>x;
        if(op==1)insert(x);
        else if(op==2)del(x);
        else if(op==3)cout<<rk(x)<<endl;
        else if(op==4)cout<<kth(x)<<endl;
        else if(op==5)cout<<pre(x)<<endl;
        else cout<<suc(x)<<endl;
    }
    return 0;
}

洛谷 P1908

思路

考虑每个值 x，答案即为 x 前面的数 >x 的数的数量。灵活运用无旋 Treap 的分裂，将树分为 \le x 和 >x 的两棵树，答案即为右树大小之和。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt,root;
struct Node
{
    int ls,rs,key,pri,sz;
}t[1000005];
void build(int x)
{
    t[++cnt].sz=1;
    t[cnt].ls=t[cnt].rs=0;
    t[cnt].key=x;
    t[cnt].pri=rand()*rand();
}
void update(int u)
{
    t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+1;
}
void split(int u,int x,int& L,int& R)
{
    if(!u)
    {
        L=R=0;
        return ;
    }
    if(t[u].key<=x)
    {
        L=u;
        split(t[u].rs,x,t[u].rs,R);
    }
    else
    {
        R=u;
        split(t[u].ls,x,L,t[u].ls);
    }
    update(u);
}
int merge(int L,int R)
{
    if(L==0||R==0)return L+R;
    if(t[L].pri>t[R].pri)
    {
        t[L].rs=merge(t[L].rs,R);
        update(L);
        return L;
    }
    t[R].ls=merge(L,t[R].ls);
    update(R);
    return R;
}
void insert(int x)
{
    int L,R;
    split(root,x,L,R);
    build(x);
    int tmp=merge(L,cnt);
    root=merge(tmp,R);
}
int rk(int x)
{
    int L,R;
    split(root,x,L,R);
    int tmp=t[R].sz;
    root=merge(L,R);
    return tmp;
}
int n,i,a,sum;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a;
        sum+=rk(a);
        //cout<<rk(a)<<endl;
        insert(a);
    }
    cout<<sum;
    return 0;
}

洛谷 P3871

思路

操作一就在平衡树中加入 a，操作二求第 \lceil\frac{n}{2}\rceil 大即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt,root;
struct Node
{
    int ls,rs,key,pri,sz;
}t[1000005];
void build(int x)
{
    t[++cnt].sz=1;
    t[cnt].ls=t[cnt].rs=0;
    t[cnt].key=x;
    t[cnt].pri=rand()*rand();
}
void update(int u)
{
    t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+1;
}
void split(int u,int x,int& L,int& R)
{
    if(!u)
    {
        L=R=0;
        return ;
    }
    if(t[u].key<=x)
    {
        L=u;
        split(t[u].rs,x,t[u].rs,R);
    }
    else
    {
        R=u;
        split(t[u].ls,x,L,t[u].ls);
    }
    update(u);
}
int merge(int L,int R)
{
    if(L==0||R==0)return L+R;
    if(t[L].pri>t[R].pri)
    {
        t[L].rs=merge(t[L].rs,R);
        update(L);
        return L;
    }
    t[R].ls=merge(L,t[R].ls);
    update(R);
    return R;
}
void insert(int x)
{
    int L,R;
    split(root,x,L,R);
    build(x);
    int tmp=merge(L,cnt);
    root=merge(tmp,R);
}
int _kth(int u,int k)
{
    if(k==t[t[u].ls].sz+1)return u;
    if(k<=t[t[u].ls].sz)return _kth(t[u].ls,k);
    if(k>t[t[u].ls].sz)return _kth(t[u].rs,k-t[t[u].ls].sz-1);
}
int kth(int k){return t[_kth(root,k)].key;}
int n,m,a,i;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a;
        insert(a);
    }
    cin>>m;
    while(m--)
    {
        string s;
        cin>>s;
        if(s=="add")
        {
            cin>>a;
            n++;
            insert(a);
        }
        else cout<<kth((n+1)/2)<<endl;
    }
    return 0;
}

序列处理

知识：排名分裂

排名分裂比起普通分裂，不一样的就是，它分裂出的是前 x 个数所形成的 Treap 以及后面所形成的 Treap。方法大同小异

合并直接和平时一样。

洛谷 P3391

思路

使用排名分裂裂出前 r 树和剩下的，再在左树中分裂出前 l-1 个，剩下的就是 [l,r]。

然后借鉴线段树，增加懒标记，这样就能从 O(n) 变成 O(\log{n})。

（翻转）其法：在序列中随便选择一个数，再将左右旁两个区间递归进行这个操作（可以证明）。这样就可以使用懒标记来加速了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt,root;
struct Node
{
    int ls,rs,pri,num,sz,lazy;
}t[1000005];
void build(int x)
{
    t[++cnt].sz=1;
    t[cnt].ls=t[cnt].rs=0;
    t[cnt].num=x;
    t[cnt].pri=rand()*rand();
}
void update(int u)
{
    t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+1;
}
void push_down(int u)
{
    if(t[u].lazy)
    {
        swap(t[u].ls,t[u].rs);
        t[t[u].ls].lazy^=1;
        t[t[u].rs].lazy^=1;
        t[u].lazy=0;
    }
}
void split(int u,int x,int& L,int& R)
{
    if(!u)
    {
        L=R=0;
        return ;
    }
    push_down(u); 
    if(t[t[u].ls].sz+1<=x)
    {
        L=u;
        split(t[u].rs,x-t[t[u].ls].sz-1,t[u].rs,R);
    }
    else
    {
        R=u;
        split(t[u].ls,x,L,t[u].ls);
    }
    update(u);
}
int merge(int L,int R)
{
    if(L==0||R==0)return L+R;
    if(t[L].pri>t[R].pri)
    {
        push_down(L);
        t[L].rs=merge(t[L].rs,R);
        update(L);
        return L;
    }
    push_down(R);
    t[R].ls=merge(L,t[R].ls);
    update(R);
    return R;
}
void output(int u)
{
    if(!u)return ;
    push_down(u);
    output(t[u].ls);
    cout<<t[u].num<<" ";
    output(t[u].rs); 
}
int n,m,x,y,i;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        build(i);
        root=merge(root,cnt);
    }
    while(m--)
    {
        cin>>x>>y;
        int L,R,p;
        split(root,y,L,R);
        split(L,x-1,L,p);
        t[p].lazy^=1;
        root=merge(merge(L,p),R);
    }
    output(root);
    return 0;
}

洛谷 P4008

思路

用变量维护光标。

插入操作就合并出整个字符串的 Treap，再分裂出前光标 -1 和剩下的，合并前光标 -1 和这个 Treap，再合并到剩下的里面。

删除操作，分裂出前光标 -1 和剩下的，在右树种分裂出前 n 个，把开始的左树和这里剩下的合并就行，中间的弃之不理就可以。

输出就分裂出前光标 -1 和剩下的，在右树中分裂出前 n 个和剩下的，在右树分裂出的左树中中序遍历输出，最后按顺序合并即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt,root;
struct Node
{
    int ls,rs,pri,sz;
    char val; 
}t[2000005];
int build(char x)
{
    t[++cnt].sz=1;
    t[cnt].ls=t[cnt].rs=0;
    t[cnt].val=x;
    t[cnt].pri=rand()*rand();
    return cnt;
}
void update(int u)
{
    t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+1;
}
void split(int u,int x,int& L,int& R)
{
    if(!u)
    {
        L=R=0;
        return ;
    }
    if(t[t[u].ls].sz+1<=x)
    {
        L=u;
        split(t[u].rs,x-t[t[u].ls].sz-1,t[u].rs,R);
    }
    else
    {
        R=u;
        split(t[u].ls,x,L,t[u].ls);
    }
    update(u);
}
int merge(int L,int R)
{
    if(L==0||R==0)return L+R;
    if(t[L].pri>t[R].pri)
    {
        t[L].rs=merge(t[L].rs,R);
        update(L);
        return L;
    }
    t[R].ls=merge(L,t[R].ls);
    update(R);
    return R;
}
void output(int u)
{
    if(!u)return ;
    output(t[u].ls);
    cout<<t[u].val;
    output(t[u].rs); 
}
int n,pos,len,i,L,R,p;
string s;
signed main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    srand(time(NULL));
    cin>>n;
    while(n--)
    {
        cin>>s;
        if(s[0]=='M')cin>>pos;
        else if(s[0]=='I')
        {
            cin>>len;
            split(root,pos,L,R);
            for(i=1;i<=len;i++)
            {
                char c=getchar();
                while(c<32||c>126)c=getchar();
                L=merge(L,build(c));
            }
            root=merge(L,R);
        }
        else if(s[0]=='D')
        {
            cin>>len;
            split(root,pos+len,L,R);
            split(L,pos,L,p);
            root=merge(L,R);
        }
        else if(s[0]=='G')
        {
            cin>>len;
            split(root,pos+len,L,R);
            split(L,pos,L,p);
            output(p);
            cout<<endl;
            root=merge(merge(L,p),R);
        }
        else if(s[0]=='P')pos--;
        else pos++;
    }
    return 0;
}

某 OJ 第二难比赛的 T6

题意