[分裂/合併式] 隨機二分查找樹 [Split / Merge] Randomized Binary Search Tree

今天來講解可以做區間處理的Randomized Binary Search Tree
好比treap，可以利用拆分跟合併的方式來做區間處理
感謝伯恩大神的指導，請參考其網站

寫起來並不會比需要旋轉的難
先定義他的節點:

	struct node{
	T data;
	int s;
	//可以再加入其他維護值(max,min等等)做區間處理用
	node *l,*r;
	node(const T &d):data(d),s(1),l(0),r(0){}
	inline void up(){
	s=1;
	if(l)s+=l->s;
	if(r)s+=r->s;
	}
	inline void down(){
	//這邊是放作區間維護需要的更新(懶惰標記下推)
	//(min,max,是否反轉區間....等等)
	//本範例只提供最基本的處理
	}
	}*root;

view raw rbst_node.cpp hosted with ❤ by GitHub

可以在裡面增加一些懶惰標記的更新(min,max,rev...等等)

計算節點大小

	inline int size(node *o){
	return o?o->s:0;
	}

view raw rbst_size.cpp hosted with ❤ by GitHub

主要利用[分裂/合併]來進行區間處理
接下來講解分裂(參見 treap分裂):

	void split(node *o,node *&a,node *&b,int k){
	if(!o)a=b=0;
	else{
	o->down();
	if(k<=size(o->l)){
	b=o;
	split(o->l,a,b->l,k);
	}else{
	a=o;
	split(o->r,a->r,b,k-size(o->l)-1);
	}
	o->up();
	}
	}

view raw rbst_split.cpp hosted with ❤ by GitHub

這是將o按中序將前k個節點分到a，剩下的分到b

合併(參見 treap合併):

	node *merge(node *a,node *b){
	if(!a||!b)return a?a:b;
	static int x;
	if(x++%(a->s+b->s)<a->s){
	a->down();
	a->r=merge(a->r,b);
	a->up();
	return a;
	}else{
	b->down();
	b->l=merge(a,b->l);
	b->up();
	return b;
	}
	}

view raw rbst_merge.cpp hosted with ❤ by GitHub

這就是隨機的精華所在
每次merge時，a有size(a)/(size(a)+size(b))的機率將a作為root
b反之亦然
而本來random是這樣寫的:

	inline int ran(){
	static int x=20160425;
	return (x=0xdefaced*x+1)&INT_MAX;
	}

view raw rbst_ran.cpp hosted with ❤ by GitHub

但是看了丁安立魔法師的blog，發現只要x++就好了，也不知道為甚麼

如果只是要做普通的二分搜尋樹，可以利用排名來求出其在整顆樹中的名次，然後再相對應處做插入

	inline int rank(const T &data){
	//使用前必須保證整顆樹是BST
	//否則會run time error
	node *p=root;
	int cnt=0;
	while(p){
	if(data<=p->data)p=p->l;
	else cnt+=size(p->l)+1,p=p->r;
	}
	return cnt;
	}
	inline void insert(const T &data,int k){
	//在第k個位置之前插入data
	node *a,*b,*now;
	split(root,a,b,k);
	now=new node(data);
	a=merge(a,now);
	root=merge(a,b);
	}

view raw rbst_rank_insert.cpp hosted with ❤ by GitHub

插入data可以寫成:
bst.insert(data,bst.rank(data));
刪除也可以用類似的方法處理

旋轉式的randomize bst就可以做這些處理了(其實分裂合併式bst速度有點慢)，那為何還需要 分裂/合併 呢?
我們可以把整顆樹的中序走訪看成是一條陣列
-->因此可以利用它來作區間的維護

像是區間的最大最小值，區間反轉啦，區間移動、刪除等等都可以利用它在logn的時間完成
只須修改其up跟down函數就可以達成目的
凡是線段樹能做到的事情，他都能做到，可以用它來解決很複雜的區間處理問題

注意的是，在有懶惰標記的情況下，如果要詢問一個區間必須在切出那塊區間後先進行down的操作再進行詢問，否則懶惰標記可能沒有被推下去，範例如下:

	/*需要再node裡面增加tag跟ma用來儲存區間增加量跟最大值*/
	int ask(node *&o,int l,int r){
	/*在o子樹詢問區間[l,r]的最大值*/
	node *a,*b,*c;
	split(o,a,b,l-1);
	split(b,b,c,r-l+1);
	b->down();/*記得要先將懶惰標記下推*/
	int ans=b->ma;
	o=merge(a,merge(b,c));
	return ans;
	}
	int add(node *&o,int l,int r,int v){
	/*在o子樹將區間[l,r]的值都加上v*/
	node *a,*b,*c;
	split(o,a,b,l-1);
	split(b,b,c,r-l+1);
	b->tag+=v;
	o=merge(a,merge(b,c));
	}

view raw rbst_ask_add.cpp hosted with ❤ by GitHub

這個範例up()跟down()也要重寫:

	inline void up(){
	size=1;
	ma=data;
	if(l){
	s+=l->s;
	ma=max(ma,l->ma+l->tag);
	}
	if(r){
	s+=r->s;
	ma=max(ma,r->ma+r->tag);
	}
	}
	inline void down(){
	data+=tag;
	if(l)l->tag+=tag;
	if(r)r->tag+=tag;
	tag=0;
	}

view raw rbst_tag_up_down.cpp hosted with ❤ by GitHub

因為應用時分靈活，故不提供樣板，只做介紹