[Split / Merge] Randomized Binary Search Tree

rbst_ask_add.cpp

/*需要再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));
} 

rbst_merge.cpp

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;
	}
}

rbst_node.cpp

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;

rbst_ran.cpp

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

rbst_rank_insert.cpp

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);
}

rbst_size.cpp

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

rbst_split.cpp

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();
	}
}

rbst_tag_up_down.cpp

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;
}