splay模板随手记

实现splay操作：

序言：

一：初始操作

1.初始化：

CPP

int rt,id;
//树根和总节点编号 
int f[N],ch[N][2],val[N];
//父亲，左右儿子，值 
int cnt[N],sz[N];
//副本数，子树大小

2.判左右儿子：

右儿子为1.左儿子为0

CPP

inline bool dir(int x){
    return x==ch[f[x]][1];
}

3.单点更新子树大小：

注意：一个节点的子树大小表示其左子树大小，右子树大小和此节点副本数之和

CPP

inline void push_up(int x){
    sz[x]=cnt[x]+sz[ch[x][0]]+sz[ch[x][1]];
}

4.单旋操作（zig,zag融合）：

CPP

inline void rotate(int x){
	int y=f[x],z=f[y];//y为x父亲，z为x祖父 
	bool r=dir(x); 
	ch[y][r]=ch[x][!r];//y代表x的子树连接x的另一子树 
	ch[x][!r]=y;//x的另一子树更新为y 
	if (z) ch[z][dir(y)]=x;
	//如果x有祖父节点，让x取代原y位置 
	if (ch[y][r]) f[ch[y][r]]=y;
	//如果y原来代表x的子树位置现有子树，让子树认y做父亲
	//第四行已经更新儿子关系，未更新父亲关系 
	f[y]=x;f[x]=z;
	//让y反认父亲，让x认祖父当父亲（取代y节点位置） 
	push_up(y);//更新y子树关系 
	push_up(x);//更新x子树关系 
}

5.splay伸展操作（将x旋转到根）：

一步到根只需转x
$>=2$ 步时判断x和y是否同侧：

(1) x和y同侧：则需要zig-zig（先转y再转x）

(2) x和y异侧：则需要zig-zag（转两次x）

CPP

inline void splay(int& z,int x){
	//z为根节点，x为上旋节点 
	int w=f[z];//设w为根节点z的父亲（当x的父亲为w时，x就是根了） 
	for (int y;(y=f[x])!=w;rotate(x))//y是x父亲 
		if (f[y]!=w)//当旋转操作还差>=2步到根时 
			rotate(dir(x)==dir(y)?y:x);
			//当x和y同为左/右子树启用zig-zig（转y 转x）
			//当x和y左右子树性质不同用zig-zag（转x 转x）
			//当旋转操作只差一步到根时只需旋转x到根 
	z=x;//把z（即rt）更新为x 
}

文章操作

实现splay操作：

序言：

一：初始操作

相关推荐

评论

splay模板随手记