Treap和Splay學習小結

最近真的是花了很大的力氣來學習平衡樹的内容，因為之前在弄偏序的時候提到了平衡樹的内容，真的是開了一個大坑啊。

先說說treap吧，網上的資料很多，描述的也很詳細，我就不細說了，這裡簡單的談談我的看法，treap就是在二叉樹的基礎上加了一個随機域來保證堆的性質

這樣可以把樹的高度維護到期望的logn級别，其他的就是一棵二叉排序樹，并沒有什麼特别的。

我實作了指針版和數組版兩種，但是說實話，在寫題的時候還是數組版的實用，無論是調試還是時間和代碼量，數組都要顯得優越很多。下面附上數組版的代碼實作

struct Treaps
{
	const static int maxn = 1e6 + 3e5;
	int L[maxn], R[maxn], v[maxn], p[maxn], A[maxn], C[maxn], tot;
	void clear(){ A[0] = L[0] = R[0] = C[0] = 0; tot = 1; }
	int Node(int V, int P){ L[tot] = R[tot] = 0; v[tot] = V; p[tot] = P; A[tot] = C[tot] = 1; return tot++; }
	void Count(int x){ C[x] = A[x] + C[L[x]] + C[R[x]]; }
	void rotate_right(int &x)
	{
		int y = L[x]; L[x] = R[y]; R[y] = x; C[y] = C[x]; Count(x); x = y;
	}
	void rotate_left(int &x)
	{
		int y = R[x]; R[x] = L[y]; L[y] = x; C[y] = C[x]; Count(x); x = y;
	}
	void Insert(int& x, int V, int P)
	{
		if (!x) { x = Node(V, P); return; }
		if (v[x] == V) ++A[x];
		else if (V < v[x])
		{
			Insert(L[x], V, P);
			if (p[x]>p[L[x]]) rotate_right(x);
		}
		else
		{
			Insert(R[x], V, P);
			if (p[x] > p[R[x]]) rotate_left(x);
		}
		Count(x);
	}
	void add(int &x, int V){ Insert(x, V, rand()); }//外部直接調用，x是樹根，v是值
	void Delete(int &x, int V)
	{
		if (!x) return;
		if (V < v[x]) Delete(L[x], V);
		else if (V > v[x]) Delete(R[x], V);
		else if (A[x] > 1) --A[x];
		else if (!L[x] || !R[x]) x = L[x] + R[x];
		else if (p[L[x]] < p[R[x]]){ rotate_right(x); Delete(R[x], V); }
		else { rotate_left(x); Delete(L[x], V); }
		Count(x);
	}
	void dec(int &x, int V) { Delete(x, V); }//外部直接調用，x是樹根，v是值
	int find(int x, int V)//傳回樹x中小于等于V的數字個數
	{
		int ans = 0;
		for (int i = x; i; i = V < v[i] ? L[i] : R[i])
		{
			if (v[i] <= V) ans += C[L[i]] + A[i];
		}
		return ans;
	}
};           

相比起treap，我覺得我對于splay的了解要深刻很多，畢竟做了那麼多題，花了那麼多時間的。

splay嚴格來講不是二叉平衡樹，但是它能保證均攤logn的效率，最神奇的是splay操作，簡直就是線段樹加強版。

相較于treap來說，splay不需要任何額外的内容，隻要保證一個splay和旋轉的操作即可，而所謂的splay操作

就是通過旋轉把一個點向上轉到目标點的操作。當然splay的具體操作等等都可以百度到，我就不多說了。

這裡也談談我的了解吧，我覺得splay的關鍵操作隻有兩個，一個是旋轉，一個是splay，下面附上代碼

struct Splays
{
	const static int maxn = 3e5 + 10;			//節點個數
	const static int INF = 0x7FFFFFFF;			//int最大值
	int ch[maxn][2], F[maxn], sz;				//左右兒子，父親節點和節點總個數
	int A[maxn];
	int Node(int f, int a) { A[sz] = a; ch[sz][0] = ch[sz][1] = 0; F[sz] = f; return sz++; }//申請一個新節點
	void clear(){ sz = 1; ch[0][0] = ch[0][1] = F[0] = 0; }//清空操作
	void rotate(int x, int k)
	{
		int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
		if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
		F[x] = F[y];    F[y] = x;	ch[x][k] = y;
		//把y的值給x，重新計算y的值
	}
	void Splay(int x, int r)
	{
		while (F[x]!=r)
		{
			if (F[F[x]] == r) { rotate(x, x == ch[F[x]][0]); return; }
			int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
			y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
		}
	}
	void insert(int &x, int a)
	{
		if (!x) { x = Node(0, a); return; }
		int now = 0;
		for (int i = x; i; i = ch[i][A[i] < a])
		{
			//下傳延遲标記
			if (!ch[i][A[i] < a]) { now = ch[i][A[i] < a] = Node(i, a); break; }
		}
		Splay(now, 0);	x = now;
	}
}solve;
           

從代碼上看是不是并沒有比treap複雜，其實的确如此，并且splay可以做到區間反轉，移動等等高難度動作，雖然treap也可強行的做，但是我覺得那樣treap本身的随機域就失去了意義了。我覺得我獨到的了解在于兩處打了注釋的地方，這是splay延遲标記的關鍵，就想線段樹區間更新一樣，我們隻要在下去的時候傳标記，上來的時候統計即可，

一開始我也是模仿他人的代碼寫的，但是呢我這個人有強波症，這個版本是我精簡多次以後确認的，雖然可能不是最短的，但我覺得應該還是很清晰的，對于不同的題目來說

splay操作是無需改動的，插入操作可能不同，旋轉操作隻有注釋的地方根據不同題目會有不同。

根據一個星期來的做題經驗，splay的題目難點在于兩個，一個是延遲标記的時候判斷細節，一個是删除操作和合并操作的細節處理，這兩個問題可以說是最為困難的，

往往是極小的一個細節錯誤就會導緻tle啊wa啊什麼的，感覺做splay的題目對于培養細心真的是很有幫助的。

推薦以下5道難題，搞定以後基本是splay大成了感覺。。

HYSBZ(BZOJ) 1500 維修數列

POJ 3580 SuperMemo

HDU 2475 Box

FZU 1978 Repair the brackets

HDU 3726 Graph and Queries

現在是1點半了，這幾天為了搞定splay我也是瘋了。。