模板傳送
FHQ-Treap顧名思義就是範浩強大佬設計的一種二叉平衡樹
下麵我們來講一下它的原理和代碼

結構體

對於一個節點，我們需要記錄的是

• 對應的值
• 子樹節點數
• 左右孩子編號
• 對應的隨機值

struct str{
	int val,size,l,r,key;
}fhq[100005];

看到這裡有人疑惑了，這個對應的隨機值是怎麼回事啊？
這裡就涉及到了一個FHQ-Treap里優化的一個小技巧
我們知道，樹在最壞的情況下，會退化成一條鏈
但很顯然，出於時間複雜度上來講，我們並不希望它成為一條鏈，因為我們的遍歷是按照一層一層來遍歷的，如果退化成一條鏈就會從最優O（log n）的複雜度直接降到O( n )，所以我們就用這個隨機的值去讓這個二叉樹變得平衡，具體怎麼去使用這個隨機值的請看函數merge

函數

首先，先給大家把主要使用的函數列出來，然後我們再一個一個講

void update(int x)
void split(int now,int dat,int &x,int &y)
int merge(int x,int y)
int add(int dat)
void ins(int dat)
void del(int dat)
int get_rk(int dat)
int get_num(int dat)
void get_pre(int dat)
void get_next(int dat)

看起來是不是很讓人頭暈眼花？
我們把函數要具體實現什麼註釋一下：

void update(int x)//更新數據
void split(int now,int dat,int &x,int &y)//分裂
int merge(int x,int y)//合併
int add(int dat)//在樹里添加節點（實際的操作）
void ins(int dat)//節點進樹（與上一個要區分開，這個只是一個輸入的對接）
void del(int dat)//節點出樹
int get_rk(int dat)//求dat數的排名
int get_num(int dat)//求排dat名的數
void get_pre(int dat)//求前驅
void get_next(int dat)//求後繼

鋪墊的差不多了，是時候開始講了

update

update函數十分簡單，主要要求實現的是更新該節點的子樹長度，因為我們會在樹上進行其他的修改操作，長度很可能會隨之變化，所以這個函數一定是要放在第一位寫的

void update(int x){//要更新x節點
	fhq[x].size=fhq[fhq[x].l].size+fhq[fhq[x].r].size+1;
        //子樹節點數=左子樹節點數+右子樹節點數+本身；
	return ;
}

split

這個函數是FHQ-Treap的重點之一，主要實現的是把一棵樹拆成兩棵樹方便後續操作，我們先解釋一下這裡的參數都是什麼意思

void split(int now,int dat,int &x,int &y)
//now表示現在遍歷到了哪個節點，dat是要從哪裡拆開這棵樹，x和y是拆後兩顆樹的根節點

因為x和y的值在函數里會被不停地更新，所以我們這裡的&x，&y就尤為重要
第一步，根據二叉搜索樹，找到從哪裡分成兩半

if(dat<fhq[now].val)//如果小，那就在now的左子樹里
	{
		y=now;//把y的值更新，縮小範圍
		split(fhq[now].l,dat,x,fhq[now].l);
	}else{//如果不小，那就在now的右子樹里
		x=now;//把x的值更新，縮小範圍
		split(fhq[now].r,dat,fhq[now].r,y);
	}

（如果看不懂的話可以自己畫個圖理解一下，本人能力有限，不會做動圖）
最後，我們就會把分裂出來的兩棵樹的根節點求出來
你以為這樣就完了嗎？還要註意幾個細節：
遞歸跳出：

if(now==0){
	x=y=0;
	return ;
}

還有！你已經修改了這棵樹了，別忘了更新！！！

update(now);

merge

來到第二個重點，也是有很多人包括剛學的我非常不理解的地方————合併函數
還是先解釋參數

int merge(int x,int y)//將以x為根的樹和以y為根的樹合併

它到底是怎麼用這些隨機值來保持平衡的呢？
我們來看一個問題：現在你有兩棵二叉搜索樹，並且告訴你一棵樹的根節點x一定比另一顆樹的根節點y要小，請問你能怎麼組合？
聰明的你肯定會想到兩種情況：

第一種是把x插進y的左子樹里，第二種是把y插進x的右子樹里

如果把這個問題交給聰明的你的話，你一定會選擇儘可能平衡的一種做法來合併，但很可惜，電腦並沒有你那麼聰明的腦子，它只會機械的執行一種操作，而這種操作執行下去就會逐漸變成一條鏈，怎麼辦呢？
這時候我們的隨機值就發揮出用場了，當面對於這樣的兩難抉擇中，它就不會再去考慮x和y的值，不會去考慮這棵二叉平衡樹（因為很顯然，前者沒必要，給你的時候就知道x小y大，後者不用管，因為怎樣操作都是一棵二叉平衡樹），而是去維護堆

註意！我在這裡是維護的小根堆！

如果我們x的key要小於y的key的話，根據小根堆我們就要把它合併到y的左子樹中

如果我們y的key要小於x的key的話，根據小根堆我們就要把它合併到x的右子樹中

（強迫症滿意地笑了）
這樣，我們就通過這些小小的隨機值完美的解決了這個難題，維護了二叉搜索樹的平衡
代碼如下

if(fhq[x].key<=fhq[y].key){
		fhq[x].r=merge(fhq[x].r,y);//y插進x的右子樹
		update(x);//別忘更新！我愛更新！警鐘長鳴！這個代碼第一次的bug就是忘更新了
		return x;//返回的是合併後的根節點
	}else{
		fhq[y].l=merge(x,fhq[y].l);//x插進y的左子樹
		update(y);//別忘更新！我愛更新！
		return y;
	}

別忘了遞歸的跳出~

if(x==0||y==0) return x+y;

add

這個函數相較於上兩個來說就簡單了
還是參數

int add(int dat)//添加一個值為dat的節點，返回該節點下標

我們只需要給它進行以下操作

fhq[++cnt].size=1;//cnt是這棵樹的總節點數
fhq[cnt].key=rand(); //取隨機值
fhq[cnt].val=dat;
return cnt;

OK力~

ins

解釋參數

void ins(int dat)//插入一個dat進樹

這裡就很好玩了，我們的操作是這樣
先通過dat值把這棵樹劈成兩半，此時一半<=dat，一半>dat

split(root,dat,x,y);//root是這棵樹的根

傳回來了兩棵樹的根節點後，我們把這個節點先悄悄的加進樹里，此時相當於有三棵樹存在

z=add(dat);

然後呢，我們要當老六，把這三棵樹再組成一棵樹

root=merge(merge(x,z),y);

這樣，我們的添加節點操作就不可思議而且妙不可言的完成了！

del

與上一個函數相反，這個函數是刪除操作

void del(int dat)//刪除值為dat的一個節點

這個操作也很妙，集中註意力
我們先通過dat值把這棵樹劈成兩半，此時一半<=dat，一半>dat

split(root,dat,x,y);

然後和上面的思想差不多，我們再從<=dat的左樹中再劈成兩半，一半是=dat的節點，一半是其他節點

split(x,dat-1,x,z);//從左樹根節點開始通過dat-1把左樹劈成一半<=dat-1,一半=dat

然後呢，我們再把這個左樹中的其他節點與右樹一合併，一個dat就自然而然的被排擠出去了！

z=merge(fhq[z].l,fhq[z].r);//這裡是重點！！！我們只需要刪除一個dat而剩下的dat還是要再加回樹里的！
root=merge(merge(x,z),y);//三塊合併

這樣這個操作也完成啦~

get_rk

這個函數是用來求值為dat的數的排名的
操作比上兩個還要簡單，我們通過dat值把這棵樹劈成兩半，此時一半<=dat，一半>dat，然後我們直接把左子樹的節點數+1就是dat數的排名了~

split(root,dat-1,x,y);
int ans=fhq[x].size+1;
merge(x,y);//分裂完別忘了合併！
return ans;

get_num

這個函數的作用是求排名為dat的數值是多少
還是分類討論的思想，我們發現這個排dat名的數要麼在當前節點的左子樹上，要麼在當前節點的右子樹上，要麼就是當前節點，然後我們就可以寫一個遞歸或迴圈來解決問題了（本人懶得寫遞歸了，如果有遞歸強迫症可以自己寫一下）

int now=root;//當前遍歷到了哪個節點
while(now){
    if(fhq[fhq[now].l].size+1==dat){//就是當前節點
	    break;
	}
	else if(fhq[fhq[now].l].size>=dat)now=fhq[now].l;//在左子樹里
	else{//在右子樹里
		dat-=fhq[fhq[now].l].size+1;//註意！右子樹比左子樹都要大！所以求的時候一定要把左子樹節點數減掉！
		now=fhq[now].r;
	}
}
return fhq[now].val;//華麗返回~

這樣就又ok了

get_pre

一個求dat前驅的函數，操作起來也很妙
我們先通過dat-1把這棵樹劈成兩半，此時一半<dat，一半>=dat
然後我們就會發現，左子樹中最大的那一個，就是dat的前驅
理解了意思，函數就好寫了

split(root,dat-1,x,y);
int now=x;
while(fhq[now].r) now=fhq[now].r;//找左子樹中最大的那一個，一定是最右的節點
cout<<fhq[now].val<<endl;
root = merge(x,y);//分裂完千萬別忘了合併！

get_next

與上面的思想相同，但是這回我們要在右子樹中找這個值：
我們先通過dat把這棵樹劈成兩半，此時一半<=dat，一半>dat
然後我們就會發現，右子樹中最大的那一個，就是dat的後繼

split(root,dat,x,y);
	int now=y;
	while(fhq[now].l) now=fhq[now].l;//找右子樹中最小的那一個，一定是最左的節點
	cout<<fhq[now].val<<endl;
    root=merge(x, y);

實現

這樣，我們就把所有的函數都捋了一遍，主函數也就好寫了，以下是完整的AC代碼

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<random>//這個裡面有rand函數，必須寫！

using namespace std;

int n;
int cnt;
int root;

struct str{
	int val,key,size,l,r;
}fhq[100005];

void update(int x){
	fhq[x].size=fhq[fhq[x].l].size+fhq[fhq[x].r].size+1;
	return ;
}

void split(int now,int dat,int &x,int &y){//分裂 
	if(now==0){
		x=y=0;
		return ;
	}
	if(dat<fhq[now].val)
	{
		y=now;
		split(fhq[now].l,dat,x,fhq[now].l);
	}else{
		x=now;
		split(fhq[now].r,dat,fhq[now].r,y);
	}
	update(now);
}

int merge(int x,int y){//合併，返回合併後的根 
	if(x==0||y==0) return x+y;
	if(fhq[x].key<=fhq[y].key){
		fhq[x].r=merge(fhq[x].r,y);
		update(x);
		return x;
	}else{
		fhq[y].l=merge(x,fhq[y].l);
		update(y);
		return y;
	}
}

int add(int dat){//增加結點 
	fhq[++cnt].size=1;
	fhq[cnt].key=rand();
	fhq[cnt].val=dat;
	return cnt;
}

void ins(int dat){//結點進樹
	int x,y,z;  
	split(root,dat,x,y);
	z=add(dat);
	root=merge(merge(x,z),y);
	return ;
}

void del(int dat){//結點出樹 
	int x,y,z; 
	split(root,dat,x,y);
	split(x,dat-1,x,z);
	z=merge(fhq[z].l,fhq[z].r);
	root=merge(merge(x,z),y);
}
int get_rk(int dat){//求dat數的排名 
	int x,y,z; 
	split(root,dat-1,x,y);
	int ans=fhq[x].size+1;
	merge(x,y);
	return ans;
} 
 
int get_num(int dat){//求排dat名的數
	int now=root;
	while(now){
        if(fhq[fhq[now].l].size+1==dat){
			break;
		}
		else if(fhq[fhq[now].l].size>=dat)now=fhq[now].l;
		else{
			dat-=fhq[fhq[now].l].size+1;
			now=fhq[now].r;
		}
	}
	return fhq[now].val;
}

void get_pre(int dat){//求前驅 
	int x,y,z; 
	split(root,dat-1,x,y);
	int now=x;
	while(fhq[now].r) now=fhq[now].r;
	cout<<fhq[now].val<<endl;
    root = merge(x,y);
}

void get_next(int dat){//求後繼 
	int x,y,z; 
	split(root,dat,x,y);
	int now=y;
	while(fhq[now].l) now=fhq[now].l;
	cout<<fhq[now].val<<endl;
    root=merge(x, y);
}

int main(){
	cin>>n;
	while(n--){
		int opt,x;
		cin>>opt>>x;
		if(opt==1) ins(x);
		else if(opt==2) del(x);
		else if(opt==3) cout<<get_rk(x)<<endl;
		else if(opt==4) cout<<get_num(x)<<endl;
		else if(opt==5) get_pre(x);
		else get_next(x);
	}
	return 0;
}

好了，看到這裡，想必你已經掌握了FHQ-Treap了，我們在下一個平衡樹相見吧！