Scapegoat Tree

__lg.cpp

namespace std{
	inline int __lg(int n){//Precondition: n >= 0
		int k=0;
		for(;n!=0;n>>=1)++k;
		return k?--k:1;
	}
}

scapegoat tree1.cpp

#ifndef NOSIZE_SCAPEGOAT_TREE
#define NOSIZE_SCAPEGOAT_TREE
#include<cmath>
#include<algorithm>
template<typename T>
class scapegoat_tree{
	private:
		struct node{
			node *ch[2];
			T data;
			node(const T&d):data(d){ch[0]=ch[1]=0;}
			node(){}
		}*root,t;
		const double alpha,loga;
		int maxn,n;
		int size(node *o){
			return o?size(o->ch[0])+size(o->ch[1])+1:0;
		}
		node *flatten(node *x,node *y){
			if(!x)return y;
			x->ch[1]=flatten(x->ch[1],y);
			return flatten(x->ch[0],x);
		}
		node *build(node *x,int n){
			if(!n){
				x->ch[0]=0;
				return x;
			}
			node *y=build(x,n/2);
			node *z=build(y->ch[1],n-1-n/2);
			y->ch[1]=z->ch[0];
			z->ch[0]=y;
			return z;
		}
		int insert(node *&o,const T&data,int dp){
			if(!o){
				o=new node(data);
				return dp<=0;
			}
			bool d=o->data<data;
			int ds1=insert(o->ch[d],data,--dp);
			if(ds1){
				int ds2=size(o->ch[!d]),n=ds1+ds2+1;
				if(ds1<=alpha*n&&ds2<=alpha*n)return n;
				o=build(flatten(o,&t),n)->ch[0];
			}return 0;
		}
		inline void success_erase(node *&o){
			node *t=o;
			o=o->ch[0]?o->ch[0]:o->ch[1];
			delete t;
		}
		bool erase(node *&o,const T&data){
			if(!o)return 0;
			if(o->data==data){
				if(!o->ch[0]||!o->ch[1])success_erase(o);
				else{
					node **t=&o->ch[1];
					for(;(*t)->ch[0];t=&(*t)->ch[0]);
					o->data=(*t)->data;
					success_erase(*t);
				}return 1;
			}else return erase(o->ch[o->data<data],data);
		}
		void clear(node *&p){
			if(p)clear(p->ch[0]),clear(p->ch[1]),delete p;
		}
	public:
		scapegoat_tree(const double&d=0.75):root(0),alpha(d),loga(log2(1.0/d)),maxn(1),n(0){}
		~scapegoat_tree(){clear(root);}
		inline void clear(){clear(root),root=0;maxn=1,n=0;}
		inline void insert(const T&data){
			insert(root,data,std::__lg(maxn)/loga);
			if(++n>maxn)maxn=n;
		}
		inline bool erase(const T&data){
			bool d=erase(root,data);
			if(d&&--n<alpha*maxn)rebuild();
			return d;
		}
		inline bool find(const T&data){
			node *o=root;
			while(o&&o->data!=data)o=o->ch[o->data<data];
			return o;
		}
		inline const T& min(){
			node *o=root;
			while(o->ch[0])o=o->ch[0];
			return o->data;
		}
		inline const T& max(){
			node *o=root;
			while(o->ch[1])o=o->ch[1];
			return o->data;
		}
		inline const T&preorder(const T&data){
			node *x=root,*y=0;
			while(x)
			if(x->data<data)y=x,x=x->ch[1];
			else x=x->ch[0];
			if(y)return y->data;
			return data;
		}
		inline const T&successor(const T&data){
			node *x=root,*y=0;
			while(x)
			if(data<x->data)y=x,x=x->ch[0];
			else x=x->ch[1];
			if(y)return y->data;
			return data;
		}
		inline void rebuild(){root=build(flatten(root,&t),maxn=n)->ch[0];}
		inline int size(){return n;}
};
#endif

scapegoat tree2.cpp

#ifndef SCAPEGOAT_TREE
#define SCAPEGOAT_TREE
#include<cmath>
#include<algorithm>
template<typename T>
class scapegoat_tree{
	private:
		struct node{
			node *ch[2];
			int s;
			T data;
			node(const T&d):s(1),data(d){}
			node():s(0){ch[0]=ch[1]=this;}
		}*nil,*root,t;
		const double alpha,loga;
		int maxn;
		inline bool isbad(node*o){
			return o->ch[0]->s>alpha*o->s||o->ch[1]->s>alpha*o->s;
		}
		node *flatten(node *x,node *y){
			if(!x->s)return y;
			x->ch[1]=flatten(x->ch[1],y);
			return flatten(x->ch[0],x);
		}
		node *build(node *x,int n){
			if(!n){
				x->ch[0]=nil;
				return x;
			}
			node *y=build(x,n/2);
			node *z=build(y->ch[1],n-1-n/2);
			y->ch[1]=z->ch[0];
			z->ch[0]=y;
			y->s=y->ch[0]->s+y->ch[1]->s+1;
			return z;
		}
		bool insert(node *&o,const T&data,int dp){
			if(!o->s){
				o=new node(data);
				o->ch[0]=o->ch[1]=nil;
				return dp<=0;
			}
			++o->s;
			if(insert(o->ch[o->data<data],data,--dp)){
				if(!isbad(o))return 1;
				o=build(flatten(o,&t),o->s)->ch[0];
			}return 0;
		}
		inline void success_erase(node *&o){
			node *t=o;
			o=o->ch[0]->s?o->ch[0]:o->ch[1];
			delete t;
		}
		bool erase(node *&o,const T&data){
			if(!o->s)return 0;
			if(o->data==data){
				if(!o->ch[0]->s||!o->ch[1]->s)success_erase(o);
				else{
					--o->s;
					node **t=&o->ch[1];
					for(;(*t)->ch[0]->s;t=&(*t)->ch[0])(*t)->s--;
					o->data=(*t)->data;
					success_erase(*t);
				}return 1;
			}else if(erase(o->ch[o->data<data],data)){
				--o->s;return 1;
			}else return 0;
		}
		void clear(node *&p){
			if(p->s)clear(p->ch[0]),clear(p->ch[1]),delete p;
		}
	public:
		scapegoat_tree(const double&d=0.75):nil(new node),root(nil),alpha(d),loga(log2(1.0/d)),maxn(1){}
		~scapegoat_tree(){clear(root),delete nil;}
		inline void clear(){clear(root),root=nil;maxn=1;}
		inline void insert(const T&data){
			insert(root,data,std::__lg(maxn)/loga);
			if(root->s>maxn)maxn=root->s;
		}
		inline bool erase(const T&data){
			bool d=erase(root,data);
			if(root->s<alpha*maxn)rebuild();
			return d;
		}
		inline bool find(const T&data){
			node *o=root;
			while(o->s&&o->data!=data)o=o->ch[o->data<data];
			return o->s;
		}
		inline int rank(const T&data){
			int cnt=0;
			for(node *o=root;o->s;)
			if(o->data<data)cnt+=o->ch[0]->s+1,o=o->ch[1];
			else o=o->ch[0];
			return cnt;
		}
		inline const T&kth(int k){
			for(node *o=root;;)
			if(k<=o->ch[0]->s)o=o->ch[0];
			else if(k==o->ch[0]->s+1)return o->data;
			else k-=o->ch[0]->s+1,o=o->ch[1];
		}
		inline const T&operator[](int k){
			return kth(k);
		}
		inline const T&preorder(const T&data){
			node *x=root,*y=0;
			while(x->s)
			if(x->data<data)y=x,x=x->ch[1];
			else x=x->ch[0];
			if(y)return y->data;
			return data;
		}
		inline const T&successor(const T&data){
			node *x=root,*y=0;
			while(x->s)
			if(data<x->data)y=x,x=x->ch[0];
			else x=x->ch[1];
			if(y)return y->data;
			return data;
		}
		inline void rebuild(){root=build(flatten(root,&t),maxn=root->s)->ch[0];}
		inline int size(){return root->s;}
};
#endif