[ Splay Tree ] 伸展樹模板

最近研究了伸展樹，它可以在均攤$\ord{logN}$的時間完成伸展操作，所謂的伸展操作就是將某個節點旋轉(rotate)到根(root)的過程，因為我們大部分在搜尋資料時，常常都只會用到特定的資料，其他大多數的資料是較少被搜尋的，因此將常被搜尋的資料靠近根是很好的策略，伸展樹由此被發明。
因為伸展樹可以分裂合併，所以可以取代分裂合併式treap或是分裂合併式randomize binary tree的功能，可以在競賽中被使用，而普通的伸展樹效率不高，故本文只介紹作區間處理的伸展樹
之後的link-cut tree會用到他，所以必須要能理解
例題: UVA 11922

定義伸展樹節點:(T為資料型態)

	struct node{
	T data;
	node *ch[2];
	int s;
	node(const T&d):data(d), s(1){}
	node():s(0){}
	/*cmp是很重要的一個函式一定要理解*/
	char cmp(int v){
	int d=v-ch[0]->s;
	if(d==1)return -1;
	return d>0;
	}
	void down(){
	/*可以加一些下推懶惰標記*/
	}
	void up(){
	s=ch[0]->s+ch[1]->s+1;
	/*可以加一些上推懶惰標記*/
	}
	}*root,*nil;

view raw splay_tree_node.cpp hosted with ❤ by GitHub

初始化時nil的l,r要指向自己

	nil=new node();
	root=nil->ch[0]=nil->ch[1]=nil;

view raw splay_tree_nil.cpp hosted with ❤ by GitHub

旋轉(跟其他樹差不多)
d=0左旋,1右旋

	void rotate(node *&a,bool d){
	node *b=a;
	a=a->ch[!d];
	b->ch[!d]=a->ch[d];
	a->ch[d]=b;
	b->up();
	a->up();
	}

view raw splay_tree_rotate.cpp hosted with ❤ by GitHub

接下來是最重要的伸展操作
這是按劉汝佳在橘色那本書的寫法實現的
主要是將第k個節點伸展到root的過程
注意!! k必須大於0

	void splay(node *&o,int k){
	o->down();
	char d1=o->cmp(k);
	if(~d1){
	if(d1)k-=o->ch[0]->s+1;
	node *p=o->ch[d1];
	p->down();
	char d2=p->cmp(k);
	if(~d2){
	int k2=d2?k-p->ch[0]->s-1:k;
	splay(p->ch[d2],k2);
	if(d1==d2)rotate(o,d1^1);
	else rotate(o->ch[d1],d1);
	}
	rotate(o,d1^1);
	}
	}

view raw splay_tree_splay.cpp hosted with ❤ by GitHub

有了splay操作，接下來是分裂&合併

	/* l不能為nil */
	node *merge(node *l,node *r){
	splay(l,l->s);
	l->ch[1]=r;
	l->up();
	return l;
	}
	/* k必須 > 0 */
	void split(node *o,node *&l,node *&r,int k){
	splay(o,k);
	l=o;
	r=o->ch[1];
	o->ch[1]=nil;
	l->up();
	}

view raw splay_tree_merge_split.cpp hosted with ❤ by GitHub

當我們要維護一個區間1~n時，可以建立0~n的splay tree，0是廢棄節點，較為方便使用

最後提供新增節點的方法:

	inline node *new_node(const T&d){
	node *o=new node(d);
	o->l=o->r=nil;
	}

view raw splay_tree_new_node.cpp hosted with ❤ by GitHub

這樣所有的操作就齊全了
剩下的一些懶惰標記跟treap一樣，可以做區間翻轉和線段樹的功能
但是請小心指標的使用
(nil為衛兵指標，方便用來編輯，若不想用可以將程式碼略為修改)