update：2023.1.12 以前寫的部落格看起來太倉促了，修改了一下。
update：2023.6.21 還是隻會寫模板的我來再修一下（其實是基本重寫了一遍~~我以前寫的什麼狗屎~~）。
第一次寫是2022.8.9，現在一看都快隔著一年了，令人感慨。

FHQ-Treap

學習這種平衡樹不需要了解 treap，據說 treap 和 splay 能幹的事情他也能幹，而且還支援可持久化。

FHQ-Treap 雖然名字裡帶 treap，但是我感覺和 treap 沒有多大的關係，主要是因為 FHQ 不需要 treap 的核心操作——旋轉。

而 FHQ 為了保持一個平衡的狀態，通過兩個基本的操作來實現其他各種操作。

前置知識

二元搜尋樹

一棵滿足以下條件的二元樹：左子樹的點的值都小於根節點的值，右子樹的點的值都大於根節點的值，且左右子樹都滿足這個性質。

堆

一種維護資料讓其最值在最上方的資料結構，比如大根堆就是大的值在上面，小的值在下面。

原理

FHQ-Treap 不是通過旋轉來保持平衡的，而是通過兩個函數 split 和 merge 。顧名思義，split 就是分裂，merge 就是合併。當然，從最底層的原理來看，還不是這兩個函數。FHQ-Treap 中的 Treap 代表 Tree + Heap，也就是說，FHQ-Treap 會按二元搜尋樹一樣根據鍵值排序結點，並且隨機賦給每個結點一個優先順序，按照二元堆積的順序排序結點（這裡用大根堆~~其實大根堆小根堆都一樣，都是為了保持平衡~~）。Treap 通過旋轉，使平衡樹同時滿足這兩個性質，從而達到平衡。而FHQ-Treap 通過呼叫 merge 函數時使平衡樹滿足堆序，實現原理與 Treap 不同，這也是為什麼我上面說不用瞭解 Treap 的原因。

變數與函數

先看一下定義的陣列：

int ch[N][2], val[N], siz[N], key[N], cnt;
int T, rt = 0;

inline void push_up(int x) {siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];}

inline int node(int x)
{
	cnt++;
	siz[cnt] = 1;
	val[cnt] = x;
	key[cnt] = rand();
	return cnt;
}

其中 ch 表示當前結點的左右兒子的編號，\(0\) 是左兒子，\(1\) 是右兒子。

val 是結點儲存的值，siz 是以當前點為根的子樹大小，key 是我們賦的隨機權值。

push_up 主要是用於更新 siz ，因為在 FHQ 中查詢有關排名之類的操作都是需要用到 siz 來判斷的，所以主要是更新子樹的大小。

node 函數的含義就是新開一個點，裡面的 key 要賦隨機權值，在初始化完之後要返回當前點的編號。

分裂與合併

按值分裂

我們先來看一下程式碼：

inline void split(int x, int k, int &xx, int &yy)
{
	if(! x) return xx = yy = 0, void();
	if(val[x] <= k) xx = x, split(ch[x][1], k, ch[x][1], yy);
	else yy = x, split(ch[x][0], k, xx, ch[x][0]);
	push_up(x);
	return ;
}

函數裡面的引數，x 是當前點的編號，k 是分裂的權值，也就是我們現在是把小於等於 k 的結點分為一棵子樹，大於 k 的結點分為一棵子樹；xx,yy 是我們分裂出來的兩棵樹的根結點。

根據二元搜尋樹的性質，我們首先是判斷當前點的值是不是小於等於 k ，如果成立則把當前 xx 替換成 x ，也就是當前結點，表示當前結點被劃分到左邊的子樹中，然後在往下遞迴，因為當前點的左子樹的值肯定小於等於 x 的權值，所以也成立，在左子樹，而右子樹的不一定會成立，所以我們去判斷右子樹。

如果要是當前點的值大於 k 的話，我們就直接把他給分給右子樹，也就是把 yy 替換成 x ，然後繼續遞迴。

我們重複上面的步驟，如果當前點是空的就直接返回不屬於任何一個結點的子節點，也就是在遞迴回去的過程中把分裂完後子節點為空的結點的 ch 給更新掉。

圖片來自OI—Wiki。

按排名分裂

其實和上面的是差不多的，就是把值改成了排名，在判斷的時候用的是 siz。

inline void split2(int x, int k, int &xx, int &yy)
{
	if(! x) return xx = yy = 0, void();
	if(siz[ch[x][0]] + 1 <= k) xx = x, split(ch[x][1], k - size[ch[x][0]] - 1, ch[x][1], yy);
	else yy = x, split(ch[x][0], k, xx, ch[x][0]);
	push_up(x);
	return ;
}

要注意在當前點被分到 xx 的時候，我們需要將 k 減去 siz[x] + 1 ，因為我們在往下是到右子樹去找，所以之前左子樹佔掉的排名個數要減去。

合併

先來看程式碼：

inline int merge(int x, int y)
{
	if(! x || ! y) return x + y;
	if(key[x] > key[y])
	{
		ch[x][1] = merge(ch[x][1], y);
		push_up(x);
		return x;
	}
	else 
	{
		ch[y][0] = merge(x, ch[y][0]);
		push_up(y);
		return y;
	}
}

我們在合併的時候，就要考慮來滿足堆的性質了，讓隨機權值最大的點在上面。

因為兩個分裂出來的子樹已經有序，所以我們在合併的時候只需要考慮把哪個樹「放在上面」，把哪個「放在下面」，也就是是需要判斷將哪個一個樹作為子樹。顯然，根據堆的性質，我們需要把 key 值大的放在上面（上面說過裡預設用大根堆）

同時，我們還需要滿足搜尋樹的性質，所以若 xx 的根結點的 key 小於 yy 的，那麼 xx 即為新根結點，並且 yy 因為 val 值比 xx 更大，應與 xx 的右子樹合併；反之，則 yy 作為新根結點，然後因為 xx 的 val 值比 yy 小，與 yy 的左子樹合併。

其他操作

插入點

split(rt, a, x, y);
rt = merge(merge(x, node(a)), y);

我們把當前的整棵樹按照給定的點的權值給分開，然後新開一個點，將其與 x 合併後再與 y 合併即可。

刪除點

split(rt, a, x, z);
split(x, a - 1, x, y);
y = merge(ch[y][0], ch[y][1]);
rt = merge(merge(x, y), z);

我們把小於等於 a 的點給分出來，然後從這棵子樹裡面把小於等於 a-1 的點給分出來，也就是我們相當於 y 中的結點全是等於 a 的，然後我們把左右兒子合併就把一個值為 a 的點給刪掉了，然後合併起來即可。

查詢給定值的排名

split(rt, a - 1, x, y);
cout << siz[x] + 1 << endl;
rt = merge(x, y);

我們先把小於等於 a-1，也就是小於 a 的值都給分出來，然後以他為根的子樹大小就是當前 a 值的排名了。

查詢給定排名的值

inline int get_rank(int x, int k)
{
	while(1)
	{
		if(k <= siz[ch[x][0]]) {x = ch[x][0]; continue;}
		if(k == siz[ch[x][0]] + 1) return x;
		else k -= siz[ch[x][0]] + 1, x = ch[x][1];
	}
}

這個沒有什麼好方法，只能暴力找，但由於我們平衡樹的優良結構，複雜度是 \(O(\log n)\) 的。

查詢前驅

split(rt, a - 1, x, y);
cout << val[get_rank(x, siz[x])] << endl;
rt = merge(x, y);

我們把小於等於 a-1 的點也就是小於 a 的點給分出來然後直接查詢我們的 x 中最後一個點的序號然後輸出對應值即可。

查詢後繼

split(rt, a, x, y);
cout << val[get_rank(y, 1)] << endl;
rt = merge(x, y);

跟上面的原理差不多，我們只不過是在大於 a 的結點的子樹中找了第一個大於 a 的點。

P3369【模板】普通平衡樹


#include <bits/stdc++.h>

#define int long long
#define N 500100

using namespace std;

int ch[N][2], val[N], siz[N], key[N], cnt;
int T, rt = 0;

inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

inline void push_up(int x) {siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];}

inline int node(int x)
{
	cnt++;
	siz[cnt] = 1;
	val[cnt] = x;
	key[cnt] = rand();
	return cnt;
}

inline int merge(int x, int y)
{
	if(! x || ! y) return x + y;
	if(key[x] > key[y])
	{
		ch[x][1] = merge(ch[x][1], y);
		push_up(x);
		return x;
	}
	else 
	{
		ch[y][0] = merge(x, ch[y][0]);
		push_up(y);
		return y;
	}
}

inline void split(int x, int k, int &xx, int &yy)
{
	if(! x) return xx = yy = 0, void();
	if(val[x] <= k) xx = x, split(ch[x][1], k, ch[x][1], yy);
	else yy = x, split(ch[x][0], k, xx, ch[x][0]);
	push_up(x);
	return ;
}

inline void split2(int x, int k, int &xx, int &yy)
{
	if(! x) return xx = yy = 0, void();
	if(siz[ch[x][0]] + 1 <= k) xx = x, split(ch[x][1], k - siz[ch[x][0]] - 1, ch[x][1], yy);
	else yy = x, split(ch[x][0], k, xx, ch[x][0]);
	push_up(x);
	return ;
}

inline int get_rank(int x, int k)
{
	while(1)
	{
		if(k <= siz[ch[x][0]]) {x = ch[x][0]; continue;}
		if(k == siz[ch[x][0]] + 1) return x;
		else k -= siz[ch[x][0]] + 1, x = ch[x][1];
	}
}

signed main()
{
	srand((unsigned)time(NULL));
	T = read();
	while(T --)
	{
		int op = read(), a = read(), x, y, z;
		if(op == 1)
		{
			split(rt, a, x, y);
			rt = merge(merge(x, node(a)), y);
		}
		if(op == 2)
		{
			
			split(rt, a, x, z);
			split(x, a - 1, x, y);
			y = merge(ch[y][0], ch[y][1]);
			rt = merge(merge(x, y), z);
		}
		if(op == 3)
		{
			split(rt, a - 1, x, y);
			cout << siz[x] + 1 << endl;
			rt = merge(x, y);
		}
		if(op == 4) cout << val[get_rank(rt, a)] << endl;
		if(op == 5)
		{
			split(rt, a - 1, x, y);
			cout << val[get_rank(x, siz[x])] << endl;
			rt = merge(x, y);
		}
		if(op == 6)
		{
			split(rt, a, x, y);
			cout << val[get_rank(y, 1)] << endl;
			rt = merge(x, y);
		}
	}
	return 0;
}

無需旋轉のFHQ-treap！