#创作计划# FHQ-Treap详解

AAA水泥批發白哥

2025-07-18 16:22:22

发布于：北京

186阅读

0回复

0点赞

0.引言

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

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

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

1.BST

BST，二叉搜索树，首先得是一颗二叉树。~~\O/\O/\O/\O/\O/\O/~~

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

那么维护这棵树就很简单了，只需要递归模拟即可。

一颗示例 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（据说好像有的能被卡到 $O(n)$ 单次）、B 树（看算导知道的，主要用于硬盘）。

3.替罪羊树

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

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

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

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

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

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

4.Treap

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

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

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

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

（标注错误， $7$ 旁应为 $7$ ）

惊人的发现，父节点的插入顺序比儿子（可以扩大到所有子孙节点）先（也可以通过 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

题意

$n$ 长的字符串 $s$ ， $q$ 次操作：操作一，将区间 $[l,r]$ 内的字符循环右移 $x$ 位；操作二，整个字符串循环右移 $x$ 位。

思路

操作 $2$ 只要把前 $n-x$ 个裂成 $L$ ，剩下后 $x$ 就是 $R$ ，合并 $R$ 和 $L$ 就行。

操作 $1$ 给每个节点加个懒标记（偏移），分裂合并的时候 pushdown（下发）和 pushup（更新大小）就行。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt,root;
struct Node
{
	int ls,rs,pri,sz,off;
	char val;
}t[2000005];
int build(char x)
{
	t[++cnt].sz=1;
	t[cnt].ls=t[cnt].rs=t[cnt].off=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 pushdown(int u)
{
	if(!u)return;
	if(t[u].off)
	{
		if(t[u].ls)t[t[u].ls].off=(t[u].off+t[t[u].ls].off)%26;
		if(t[u].rs)t[t[u].rs].off=(t[u].off+t[t[u].rs].off)%26;
		int add=(t[u].off+26)%26;
		char newc='a'+(t[u].val-'a'+add)%26;
		if(newc>'z')newc-=26;
		else if(newc<'a')newc+=26;
		t[u].val=newc;
		t[u].off=0;
	}
}
void split(int u,int x,int& L,int& R)
{
	if(!u)
	{
		L=R=0;
		return ;
	}
	pushdown(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)
	{
		pushdown(L);
		t[L].rs=merge(t[L].rs,R);
		update(L);
		return L;
	}
	pushdown(R);
	t[R].ls=merge(L,t[R].ls);
	update(R);
	return R;
}
void output(int u)
{
	if(!u)return ;
	pushdown(u);
	output(t[u].ls);
	cout<<t[u].val;
	output(t[u].rs); 
}
int n,q,l,r,x,i,L,R,p,op;
string s;
signed main()
{
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	srand(time(NULL));
	cin>>n>>s>>q;
	for(i=0;i<n;i++)root=merge(root,build(s[i]));
	while(q--)
	{
		cin>>op;
		if(op==1)
		{
			cin>>l>>r>>x;
			split(root,l-1,L,R);
			split(R,r-l+1,p,R);
			if(p)
			{
				t[p].off=(t[p].off+(x%26))%26;
				if(t[p].off<0)t[p].off+=26;
			}
			root=merge(merge(L,p),R);
		}
		else
		{
			cin>>x;
			x%=n;
			if(x==0)continue;
			split(root,n-x,L,R);
			root=merge(R,L);
		}
	}
	output(root);
	return 0;
}