Treap 弱平衡的隨機性很強的老鼠看不懂的平衡樹

Q:為什麼叫 Treap?
A:看看二叉搜索樹(BST)和堆(Heap)，組合起來就是 Treap

其中，二叉搜索樹的性質是：
左子節點的值 (val) 比父節點小
右子節點的值 (val) 比父節點大

如果這些節點的值都一樣，這棵樹就會退化成一顆（？）鏈。

對， 我知道你在想什麼——並查集。
雖然都會被傻老鼠亂搞退化成鏈，但優化方式大有不同。

優化 - Priority - 玄學抽卡

笨蛋老鼠可能還有疑惑，為什麼鏈是naive的而樹是超棒的呢？
從OIwiki偷兩張圖來解釋：
看，這是一顆正常的樹，基本上可以看作滿二叉樹，一次查詢只需要 \(O(\log_2{n})\)的時間複雜度

這是一顆（？）被老鼠亂搞以後形成的鏈，一次查詢的時間複雜度劣化到了 \(O(n)\)

那麼，既然屑老鼠已經說了這棵樹有堆的性質，所以就要給每一個結點上一個隨機的優先順序\(Priority\)
讓它同時成為一個堆，在雙重特征下保持完全二叉樹的形狀

PS:傻老鼠腦子糊塗了，首先樹得滿足BST的性質，然後空下來時維護Heap的性質

大功告成，現在該知道節點裡面應該放什麼了。

struct node{
	node *child[2];
	int val,ranf,cnt,siz;
	node(int __val) : val(__val), cnt(1), siz(1){
		child[0] = child[1] = nullptr;//左右兒子初始化 
		ranf = rand();//玄學抽卡 
	} 
	node(node *__node){
		val = __node->val, ranf = __node->ranf, cnt = __node->cnt, siz = __node->siz;
	}
	void ud_siz(){
		siz = cnt;
		if(child[0] != nullptr)siz += child[0]->siz;
		if(child[1] != nullptr)siz += child[1]->siz; 
	}
};

Treap的重要操作 Split & Merge

分裂過程接受兩個參數：根指針 \(\textit{cur}\)、關鍵值 \(\textit{key}\)。結果為將根指針指向的 treap 分裂為兩個 treap，第一個 treap 所有結點的值\(\textit{val}\)小於等於 \(\textit{key}\)，第二個 treap 所有結點的值大於 \(\textit{key}\)。
該過程首先判斷 \(\textit{key}\) 是否小於 \(\textit{cur}\) 的值，若小於，則說明 \(\textit{cur}\) 及其右子樹全部大於 \(\textit{key}\)，屬於第二個 treap。當然，也可能有一部分的左子樹的值大於 \(\textit{key}\)，所以還需要繼續向左子樹遞歸地分裂。對於大於 \(\textit{key}\) 的那部分左子樹，我們把它作為 \(\textit{cur}\) 的左子樹，這樣，整個 \(\textit{cur}\) 上的節點都是大於 \(\textit{key}\) 的。
相應的，如果 \(\textit{key}\) 大於等於 \(\textit{cur}\) 的值，說明 \(\textit{cur}\) 的整個左子樹以及其自身都小於 \(\textit{key}\)，屬於分裂後的第一個 treap。並且，\(\textit{cur}\) 的部分右子樹也可能有部分小於 \(\textit{key}\)，因此我們需要繼續遞歸地分裂右子樹。把小於 \(\textit{key}\) 的那部分作為 \(\textit{cur}\) 的右子樹，這樣，整個 \(\textit{cur}\) 上的節點都小於 \(\textit{key}\)。
下圖展示了 \(\textit{cur}\) 的值小於等於 \(\textit{key}\) 時按值分裂的情況. ——OIWIKI

老鼠才不會解釋，因為老鼠沒腦子。

pair<node *, node *> split(node *rt,int key){
	if(rt == nullptr)return {nullptr, nullptr};
	if(rt->val <= key){
	auto temp = split(rt->child[1],key);
		rt->child[1] = temp.first;
		rt->ud_siz();
		return {rt,temp.second};
	}
	else{
		auto temp = split(rt->child[0],key);
		rt->child[0] = temp.second;
		rt->ud_siz();
		return {temp.first,rt};
	}
	}

合併過程接受兩個參數：左 treap 的根指針 \(\textit{u}\)、右 treap 的根指針 \(\textit{v}\)。必須滿足 \(\textit{u}\) 中所有結點的值小於等於 \(\textit{v}\) 中所有結點的值。一般來說，我們合併的兩個 treap 都是原來從一個 treap 中分裂出去的，所以不難滿足 \(\textit{u}\) 中所有節點的值都小於 \(\textit{v}\)
在旋轉 treap 中，我們藉助旋轉操作來維護 \(\textit{priority}\) 符合堆的性質，同時旋轉時還不能改變樹的性質。在無旋 treap 中，我們用合併達到相同的效果。
因為兩個 treap 已經有序，所以我們在合併的時候只需要考慮把哪個樹「放在上面」，把哪個「放在下麵」，也就是是需要判斷將哪個一個樹作為子樹。顯然，根據堆的性質，我們需要把 \(\textit{priority}\) 小的放在上面（這裡採用小根堆）。
同時，我們還需要滿足搜索樹的性質，所以若 \(\textit{u}\) 的根結點的 \(\textit{priority}\) 小於 \(\textit{v}\) 的，那麼 \(\textit{u}\) 即為新根結點，並且 \(\textit{v}\) 因為值比 \(\textit{u}\) 更大，應與 \(\textit{u}\) 的右子樹合併；反之，則 \(\textit{v}\) 作為新根結點，然後因為 u 的值比 \(\textit{v}\) 小，與 v 的左子樹合併。——OIWIKI
老鼠懶，自己看。

node *merge(node *u,node *v){
		if(u == nullptr && v == nullptr)return nullptr;
		if(u != nullptr && v == nullptr)return u;
		if(u == nullptr && v != nullptr)return v;
		if(u->ranf < v->ranf){
			u->child[1] = merge(u->child[1],v);
			u->ud_siz();
			return u;
		}
		else{
			v->child[0] = merge(u, v->child[0]);
			v->ud_siz();
			return v;
		}
	}

不好用，才不用——⑨老鼠

作為笨蛋老鼠，能看懂這個東西怎麼用才奇怪吧，只能分裂和合併的數據結構，鬼才用嘞！
笨蛋老鼠！這個東西可以整很多活的

查詢小於等於val的數的個數：考察根節點的值和val，如果val小於根節點，遞歸進左子樹，否則遞歸進右子樹。
插入val：先查詢Rank(val)，然後按照rank把整個TreapSplit成兩個，把val做成一個新節點，Merge到裡面。
刪除val：先查詢Rank(val)，然後按照rank把整個TreapSplit成三個，刪除需要的點，最後Merge剩下兩個。
查詢第K個值：把整個TreapSplit成三個，輸出需要的值，最後合併起來。

好啊，你的區間呢？

誇下的海口終究會被打qwq。
發現了沒，這些個操作全是區間的，想想你的線段樹怎麼區間修改優化的？
\(LazyTag\)救我狗命對吧！
所以，直接打標記建線段樹到處亂搞，怎麼在樹鏈剖分上整的活大多數都能整！