splay 学习笔记

发表于
不严谨的 Splay 学习记录

前置知识

排序二叉树

简单的说，就是每个结点的左子树中的每个数都小于该节点，且右子树中的每个数都大于该节点。

重点问题

对于普通的排序二叉树，很容易通过特殊数据卡你。那就需要通过旋转将出题人精心设计的数据打乱。

旋转操作

若 $u$ 是 $v$ 的左儿子，且要将 $u$ 旋转到 $v$ 处：

先断开 $u$ 和 $v$ 以及 $u$ 和他的右儿子，然后交换处理 $u$ 和 $v$ ，最后把儿子接回去。

若 $u$ 是 $v$ 的右儿子同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
void ziag(int x){
	if(!fa[x]||!x)return;
	int f=fa[x];
	int sson=son[f][1]==x,sonn=son[fa[f]][1]==f;
	fa[x]=fa[f];
	son[f][sson]=son[x][sson^1];
	if(son[x][sson^1])fa[son[x][sson^1]]=f;
	son[x][sson^1]=f;
	son[fa[f]][sonn]=x;
	fa[f]=x;
	pull_up(x);
	pull_up(f);
}

但是，如果全部按一个方向旋转，则常数较大，达不到优化效果。

伸展操作

如果儿子与父亲在一侧，且要把儿子旋转到根节点，则应该先将父亲转到根节点，再将儿子与父亲旋转。否则连续两次旋转儿子。

1
2
3
4
5
6
7
8
9
void splay(int x,int ed){//表示将x旋转成为ed的儿子
	while(fa[x]!=ed){
		int f=fa[x],ff=fa[f];
		if(ff==ed)ziag(x);
		else if((son[ff][1]==f)==(son[f][1]==x))ziag(f),ziag(x); 
		else ziag(x),ziag(x);
	}
	if(ed==0)root=x;
}

插入操作

如果当前树为空，则新建结点并更新树根；如果当前树非空，则递归找到应更新的位置，并新建结点或直接更新结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void insert(int x,int f){
	if(!root){
		root=++cnt;
		val[cnt]=x;
		num[cnt]=sz[cnt]=1;
		return ;
	}
	if(x==val[f]){
		sz[f]++,num[f]++;
		splay(f,0);
		return;
	}
	if(x<val[f]){
		if(!son[f][0]){
			son[f][0]=++cnt;
			fa[cnt]=f;
			val[cnt]=x;
			num[cnt]=sz[cnt]=1;
			splay(cnt,0);
			return;
		}
		insert(x,son[f][0]);
	}
	else{
		if(!son[f][1]){
			son[f][1]=++cnt;
			fa[cnt]=f;
			val[cnt]=x;
			num[cnt]=sz[cnt]=1;
			splay(cnt,0);
			return;
		}
		insert(x,son[f][1]);
	}
}

查询操作

首先插入要查询的数，然后递归查找，如果发现当前节点就是答案，需要将当前节点转动成根节点的儿子，最后删除查询的数。注意分清：查询排名/位置，前驱/后继。

  • 查排名为 $x$ 的数：如果左子树大于 $x$ ，在左子树中找；然后考虑当前结点；最后考虑右子树。

  • 查 $x$ 数的排名：先找到当前的数，再累计算答案。注意答案要随着递归更新。

  • 查前驱：先转到根，再找左子树中最大的。

  • 查后继：先转到根，再找右子树中最小的。

删除操作

首先递归找到要删除的结点，然后将其转到叶子，最后直接砍断该节点与父节点的联系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void dele(int x,int now){
	if (val[now] == x) {
        while (son[now][0] || son[now][1]) {
            if (son[now][0]) {
				if(now==root)root=son[now][0];
                ziag(son[now][0]);            
                continue;
            }
			if(now==root)root=son[now][1];
            ziag(son[now][1]);        
        }
        sz[now]--, num[now]--;
        if (num[now]) {
            pull_up(now);
            return;
        }
        int sson = son[fa[now]][1] == now;          
        pull_up(now);
		son[fa[now]][sson] = 0; 
		fa[now] = 0;
        return;
    }
	if(val[now]<x)dele(x,son[now][1]);
	else dele(x,son[now][0]);
}

区间翻转操作

假设我们要翻转区间 $[l,r]$，那我们先把 $l-1$ 转到树根，再把 $r+1$ 转成树根的右儿子，则我们要翻转的区间是此时 $r+1$ 的左子树。类似线段树的方式采用懒标记，注意在以下地方需要更新：

  • 每一个旋转操作（先更新父亲，再更新儿子）

  • 每一个查询操作

注意上述的 $l$ 和 $r$ 是位置，相当于排名，所有还要记得查找真正的值。

1
2
3
4
5
6
7
8
9
10
11
12
void push_down(int x){
	if(!x||!lazy[x])return;
	lazy[x]=0;
	swap(son[x][0],son[x][1]);
	if(son[x][0])lazy[son[x][0]]^=1;
	if(son[x][1])lazy[son[x][1]]^=1;
}
void modify(int l,int r){//这个函数不完整哟
	splay(l,0);
	splay(r,root);
	lazy[son[son[root][1]][0]]^=1;
}

玄学优化

由于这玩意常数比较大而且不太稳定，考虑随机优化：每个插入、查询操作后随机选取一个数旋转到根。这样大概能跑得快那么一点点（其实快不少）。