Splay 树

Splay 树

定义

Splay 是一种高效的 BST，平摊复杂度为 \(O(\log n)\)，可以快速访问热数据

rotate+splay 精华部分

splay双旋

一字旋：先fa再x

之字旋：先x再fa

旋根操作：最麻烦的地方，注意y每次循环要给他赋值

void rotate(int x){
	int y=t[x].fa,z=t[y].fa,k=t[y].son[1]==x;
	t[y].son[k] = t[x].son[k^1];
	t[t[y].son[k]].fa = y;
	t[x].son[k^1] = y;
	t[y].fa = x;
	if(z)t[z].son[t[z].son[1]==y]=x;
	t[x].fa = z;
	pushup(y);pushup(x);
}
void splay(int x,int goal){
	int y;
	while((y=t[x].fa)!=goal){
		if(t[y].fa!=goal)
			rotate((t[t[y].fa].son[1]==y)^
				(t[y].son[1]==x)?x:y);//不要调换x,y 
		rotate(x);
	}
	if(goal==0)root=x;
}

find 实用操作

BST的通用函数，注意要pushdown，因为其他操作要先调用它，所以免去splay时pushdown的麻烦事

int find(int p,int x){
	pushdown(p);
	if(x==t[ls(p)].siz+1)return p;
	if(x<=t[ls(p)].siz)return find(ls(p),x);
	return find(rs(p),x-t[ls(p)].siz-1);
}

split 关键操作

注意 split 修改完指定区间后要对root做pushup

void split(int l,int r){//钦定为ls(rs(root)) 
	int p=find(root,l-1),q=find(root,r+1);
	splay(p,0);
	splay(q,p);
}

build 必要操作

也要 pushup

void build(int &p,int L,int R,int Fa){
	if(L>R)return;
	p = mknode();
	t[p].fa = Fa;
	int mid=L+R>>1;
	t[p].val = a[mid];
	t[p].id = mid;
	if(L==R){
		t[p].sum = t[p].mx = a[L];
		t[p].rmx = t[p].lmx = max(a[L],0);
		t[p].siz = 1;
		return;
	}
	build(ls(p),L,mid-1,p);
	build(rs(p),mid+1,R,p);
	pushup(p);
}

复杂度

使用平摊分析的势能分析，插入删除的平摊费用为 \(O(\log n)\)

练习题

[NOI2005] 维护数列 提示：splay树

[AHOI2006] 文本编辑器 提示：splay树

【模板】文艺平衡树

[TJOI2007] 书架