伸展树（Splay）基本操作

1.旋转操作

inline void rotate(int x) //左旋和右旋操作 
{
	int y=fa[x],z=fa[y];//y是x的父节点，z是y的父节点 
	int b=(lc[y]==x)?rc[x]:lc[x];
	//if(x==lc[y]) b=rc[x];反之。选取不与y->x同侧的x的儿子b 
	fa[x]=z,fa[y]=x;
	if(b) fa[b]=y;//调整父子关系 
	if(z) (y==lc[z]?lc[z]:rc[z])=x;
	if(x==lc[y]) rc[x]=y,lc[y]=b;
	else lc[x]=y,rc[x]=b;//进一步调整左右子树关系 
}

2.Splay（x,target)     将伸展树中的节点x调整为target的左/右儿子，若要将x调整为根节点，将target设置为空节点即可。

inline void Splay(int x,int tar){
	while(fa[x]!=tar){
		if(fa[fa[x]]!=tar)
			Wrt(x)==Wrt(fa[x])?rotate(fa[x]):rotate(x);
		rotate(x); 
	}
	if(!tar) rt=x;
}

inline bool Wrt(int x)//判断x是否是父亲的右儿子 
{
	return rc[fa[x]]==x;
}

3.find(v)    判断v是否在伸展树中

inline void find(int v)
{
	int x=root;	//从根开始查找 
	while(x){
		if(v==val[x]) break;//找到了 
		if(v>val[x]) x=rc[x];//v比x权值大，在右子树中寻找 
		else x=lc[x];
	}
	if(x) Splay(x,0);//调整伸展树形态 
	return x;
} 

4.insert(v)    将v插入伸展树中

inline void insert(int v)//插入 
{
	int x=root,y,dir;//dir用于判断是右还是左
	while(x)
	{
		++sze[y=x];
		if(v


5.join(u,v)    将两棵伸展树s1 s2合并，u，v分别是这两棵树的根节点,且s1中所有元素都小于s2
具体方法：找到s1中权值最大的节点x，将其调整为根节点，将s2作为x的右子树

inline void join(int u,int v)
{
	fa[u]=fa[v]=0;
	int w=u;
	while(rc[w]) w=rc[w];
	Splay(w,0);//将w调整为根节点 
	rc[w]=v,fa[v]=w; 
}
 



6.delete(x)    删除x
执行Splay(x,0),然后join(lc[x],rc[x])即可。

inline void delete(int u)
{
	Splay(x,0);
	if(!lc[u]||!rc[u]) fa[root=lc[u]+rc[u]]=0;
	else join(lc[u],rc[u]);
	lc[u]=rc[u]=0;
} 



7.getrank(v)    查询v的排名(例如按权值从小到大排序）
首先查找到v，执行Splay(x,0), v的排名就是左子树节点个数+1

inline void getrank(int v)
{
	int x=find(v);
	return sze[lc[x]]+1;
}



8.Spilt(v)    以v为界，将伸展树分离成s1和s2，其中s1所有元素都小于s2
首先执行find(v),将其调整为根节点即可。代码就不赘述。


此上为八种基本操作。