splay学习笔记

splay学习笔记

前言

splay是序列之王——WerKeyTom_FTD

splay是个有用的东西

早就想学了，以前一直学不会。

splay博大精深，下面的东西没有仔细检查，可能有错误。

这其实就是一个模板库。

ps:我才不会告诉你我打排序机械臂的时候调了一个半小时发现排序打错了

我也不会告诉你我地震那题调了两个晚上发现“在x之后插入”看成了“在x之前插入”

正文

splay的基本功能

在O((log_n))的时间里进行二叉搜索树中的

插入、删除、查找、翻转、合并等

常数巨大，实现简单

!!!注意事项

1. 进行了有关点的操作都要把点旋到根，一方面便于操作，另一方面维护树的平衡。

2. 改变了节点的儿子（尤其是增加一个儿子）之后一定要用splay操作把那个儿子旋到根，不能用update操作，要不然会错（我也不知道为什么），一定要注意，把新增的那个节点旋到根而不是旋它的父亲，这个错误很隐蔽

3. 标记是在每一次访问到一个新的节点时就要pushdown的,一定要时刻牢记！最好进行任何操作之前都用一下find来更新标记

4. splay中懒标记的含义应是“这个节点已经更新了，但儿子还未更新”而不是“这个节点和儿子都没有更新”，这样避免update(x)的时候x的儿子还未被标记更新

   补充：懒标记的处理

   首先，我们在每次将k和k+tot+1移到对应的位置时，需要一个类似查找k大值的find操作，即找出在平衡树中，实际编号为k在树中中序遍历的编号，这个才是我们真正需要处理的区间端点编号，那么就好了，我们只需在查找的过程中下传标记就好了！（其实线段树中也是这么做的），因为我们所有的操作都需要先find一下，所以我们可以保证才每次操作的结果计算出来时，对应的节点的标记都已经传好了。而我们在修改时，直接修改对应节点的记录标记和懒标记，因为**我们的懒标记记录的都是已经对当前节点产生贡献，但是还没有当前节点的子树区间产生贡献！**然后就是每处有修改的地方都要update一下就好了。

   By Hello World!

5. 增加数字为-INF和INF的两个哨兵节点，因为如果对区间1_{x或 x}n操作，用到前后的节点就需要1和n+2。它们的cnt可以设为0，**需要注意的是，它们以及节点0的key,ma,ch,fa等值应该时刻保持一个不会影响答案的值，或者是在update与pushdown函数中特判。在题目有区间修改的时候（如最大值2等题目）要特别注意。**其实一般只要把key,ma设为-INF就好了。为什么这样不会影响区间和之类的答案呢？因为每次我们查询的区间都是一定不包含哨兵节点的呀。只要每次查询的时候正确update，查询到的结果是不包括哨兵的。

6. 区分一个节点的排名和这个节点的键值：这个节点的排名是它是当前数组中的第几个，用左儿子的size+1表示；这个节点的键值是题目中输入的数字。在有区间翻转的题目中尤其容易出错

7. 可以建一个回收站（栈233）来存放删除的节点的编号，节省空间

8. 类似排序机械臂的题目，splay实际是按在序列中的位置来排序的，这是我们无法查找权值第k小的节点。怎么解决呢？把原始序列排个序就可以轻松找到第k小的数了。

update(x)

在rotate的时候更新节点的各个数值

根据需要打这个函数吧

void update(int x)
{
	tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+1;//记得加上自身的那一个，这一点和线段树不一样
	tree[x].ma=max(max(tree[tree[x].ch[0]].ma,tree[tree[x].ch[1]].ma),tree[x].key);//这里可以特判一下，防止x的儿子是哨兵或者0，影响答案。
}

pushdown(x)

把x的懒标记下传

注意：这里的标记的含义应是“这个节点已经更新了，但儿子还未更新”而不是“这个节点和儿子都没有更新”，这样在find或remove的时候可以把x的儿子给更新上，避免update(x)的时候x的儿子还未被标记更新

void pushdown(int x)
{
	if (tree[x].ch[0])//这一个判断很重要
	{
		tree[tree[x].ch[0]].add+=tree[x].add;
		tree[tree[x].ch[0]].ma+=tree[x].add;
		tree[tree[x].ch[0]].key+=tree[x].add;
	}
	if (tree[x].ch[1])//这一个判断很重要
	{
		tree[tree[x].ch[1]].add+=tree[x].add;
		tree[tree[x].ch[1]].ma+=tree[x].add;
		tree[tree[x].ch[1]].key+=tree[x].add;
	}
	tree[x].add=0;
}

rotate(x)

把一个节点x旋转到父亲y的位置

void rotate(int x)
{
	int y=tree[x].fa;
	int z=tree[y].fa;
	int k=get(x);
	int kk=get(y);
	if (z!=0)//重要
	tree[z].ch[kk]=x;
	tree[x].fa=z;
	tree[y].ch[k]=tree[x].ch[k^1];
	if (tree[x].ch[k^1]!=0)//重要
	tree[tree[x].ch[k^1]].fa=y;
	tree[x].ch[k^1]=y;
	tree[y].fa=x;
	update(y);update(x);
}

splay(x,y)

把一个点x向上旋转到y的儿子处（y=0时x旋到根）

void deal(int x,int goal)
{
	list[0]=0;
	for (x=x;x!=goal;x=tree[x].fa);
	list[++list[0]]=x;
	for (int i=list[0];i>=1;i--)
		pushdown(list[i]);
}

void splay(int x,int goal)//将x旋转为goal的儿子，如果goal是0则旋转到根
{
    deal(x,goal);//这一段用来更新懒标记。如果严格按照每次操作点之前都进行find操作的话就不用加，保险起见最好加上
	while (tree[x].fa!=goal)
	{
		int y=tree[x].fa;
		int z=tree[y].fa;
		if (z!=goal)//很重要，如果x再旋一下就到goal儿子的话，就不用这一步了！！
		{
			if (get(x)==get(y)) //若x与y共线则双旋，即先旋y
				rotate(y);
			else 
                rotate(x);
		}
		if (y!=0)
		rotate(x);//无论怎样最后都旋x
	}
	if (tree[x].fa==0) root=x;//如果goal是0，则将根节点更新为x
}

insert(x)

插入键值为x的点

先找到x的位置，若已有就把cnt++，若没有就新建节点

然后把这个点旋到根

注意：这一步操作有多种打法，比如可以把前驱旋到根，把后继旋到根的右儿子，再断开连接，新建节点为根等。不过我还没打过，不知道有没有问题。

方法一：

void insert(int key)//splay按键值排序，插入一个键值为key的点
{
	int x=root,fa=0;
	while ((x!=0)&&(tree[x].key!=key))//当x存在并且没有移动到当前的值
	{
        pushdown(x);//记得更新标记！
		fa=x;
		if (tree[x].key>key) x=tree[x].ch[0];
		else x=tree[x].ch[1];
	}
	if (x!=0)
	{
		tree[x].cnt++;//键值为key的节点已存在，直接cnt++
	}
	else//键值为key的节点不存在，新建节点
	{
		x=++tot;
		if (fa!=0)
		{
			if (key<tree[fa].key)
			tree[fa].ch[0]=x;
			else
			tree[fa].ch[1]=x;
			tree[fa].size++;
		}
		
		tree[x].fa=fa;
		tree[x].cnt=1;
		tree[x].size=1;
		tree[x].key=key;
		tree[x].ch[0]=tree[x].ch[1]=0;
	}
	splay(x,0);//把当前位置移到根，保证结构的平衡。注意前面因为更改了子树大小，所以这里必须Splay上去进行update保证size的正确。
}

方法二：

void insert(int x,int y)//splay按在序列中的位置排序，在第x个数前插入一个数y
{
	int kk;
	find(x+1);//由于增加了哨兵节点，应查找x+1;
	kk=root;
	find(x);//由于增加了哨兵节点，应查找x;
	splay(kk,root);//重要！！刚find完时kk不一定是root的儿子
	int k=tree[root].ch[1];
	tree[k].ch[0]=++tot;
	tree[tot].ch[0]=tree[tot].ch[1]=0;
	tree[tot].fa=k;
	tree[tot].cnt=1;
	tree[tot].key=y;
	update(tot);
	splay(tot,0);
}

---

build(l,r,fa)

如果题目给定了初始序列，可以用这种方式建立一颗平衡的splay tree。当然，暴力一个个insert也是可以的

int build(int l,int r,int fa)//函数是有返回值的！
{
	if (l>r) return 0;//记得设出口
	int mid=(l+r)/2;
	int x=++tot;//tot是会变的，这里先记录
	tree[x].fa=fa;
	tree[x].cnt=1;
	tree[x].key=mid;
	tree[x].size=1;
	tree[x].ch[0]=build(l,mid-1,x);
	tree[x].ch[1]=build(mid+1,r,x);
	update(x);//记得update
	return x;//记得返回当前子树的根
}

find(key)

寻找键值为key的节点，若不存在则找到它的前驱或后继，然后把它旋到根

注意：这里的平衡树是按键值排序的，有的平衡树是按编号排序的，这个时候这种打法是无效的

void find(int key)
{
	int x=root;
	while (tree[x].key!=key)
	{
        pushdown(x);//记得一路pushdown
		if (tree[x].key>key)
		{
			if (tree[x].ch[0]==0) break;//此时找不到键值为key的点，找到它的后继
			x=tree[x].ch[0];
		}
		else 
		{
			if (tree[x].ch[1]==0) break;//此时找不到键值为key的点，找到它的前驱
			x=tree[x].ch[1];
		}
	}
    pushdown(x);//记得一路pushdown
	splay(x,0);//把它旋到根
}

kth(s)

查找平衡树里第s大的数

注意：如果平衡树按照在序列中的位置排序，这个操作是查找序列第k个数。要找序列第k小的话要再开一颗线段树或用其他奇技淫巧。

int kth(int k)
{
	int x=root;
	while (1)
	{
		int left=tree[x].ch[0];
		if (tree[left].size>=k)
			x=left;
		else
		{
			if (tree[left].size+tree[x].cnt<k)
				k-=tree[left].size+tree[x].cnt,x=tree[x].ch[1];
			else
			return x;
		}
	}
}

reverse(x,y)

翻转一段区间

void reverse(int l,int r)//翻转第l个数到第r个数 
{
	int x,y;
	find(l);
	x=root;
	find(r+2);
	y=root;
	splay(x,y);
	tree[tree[x].ch[1]].rev^=1;
    swap(tree[tree[x].ch[1]].ch[0],tree[tree[x].ch[1]].ch[1]);//tag指“这个节点已经更新了，但儿子还未更新”
}

后记

在断断续续学习了一个星期后，把splay的经典例题都做了一遍。列个清单：

【jzoj】排序机械臂、地震、最大值2、GSS6、维护序列

【洛谷】普通平衡树、文艺平衡树

【LOJ】维护全序集

维护全序集

这是一道模板题，其数据比「普通平衡树」更强。

如未特别说明，以下所有数据均为整数。

维护一个多重集 ，初始为空，有以下几种操作：

1. 把 x 加入 S 2. 删除 S 中的一个x，保证删除的x一定存在 3. 求S中第k小 4. 求S中有多少个元素小于x 5. 求S中小于x的最大数 6. 求 S 中大于x的最小数

操作共 n 次

$1leq n leq 3*10^{5,0 leq x leq 10}9$

这一个代码比较优美

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct qy
{
	int ch[2],fa,key,size,cnt;
};

int n,i,type,x,root,tot,ans,cnt;
qy tree[1000005];

int get(int x)
{
	if (tree[tree[x].fa].ch[0]==x) return 0;
	else return 1;
}

int update(int x)
{
	tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+tree[x].cnt;
}

void rotate(int x)
{
	int y=tree[x].fa; int z=tree[y].fa;
	int k=get(x); int kk=get(y);
	if (z)
	tree[z].ch[kk]=x;
	tree[x].fa=z;
	tree[y].ch[k]=tree[x].ch[k^1];
	if (tree[x].ch[k^1])
	tree[tree[x].ch[k^1]].fa=y;
	tree[x].ch[k^1]=y;
	tree[y].fa=x;
	update(y);update(x);
}

void splay(int x,int goal)
{
	while (tree[x].fa!=goal)
	{
		int y=tree[x].fa;
		if (tree[y].fa!=goal)
		{
			if (get(y)==get(x)) rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if (goal==0) root=x;
}

void find(int key)
{
	int x=root;
	while (1)
	{
		if (tree[x].key<key)
		{
			if (tree[x].ch[1]) x=tree[x].ch[1];
			else break;
		}
		else
		{
			if (tree[x].key>key)
			{
				if (tree[x].ch[0]) x=tree[x].ch[0];
				else break;
			}
			else
			break;
		}
	}
	splay(x,0);
}

int last(int key)
{
	int x;
	find(key);
	if (tree[root].key<key) return root;
	else
	{
		x=tree[root].ch[0];
		while (tree[x].ch[1]!=0)
			x=tree[x].ch[1];
		return x;
	}
}

int next(int key)
{
	int x;
	find(key);
	if (tree[root].key>key) return root;
	else
	{
		x=tree[root].ch[1];
		while (tree[x].ch[0]!=0)
			x=tree[x].ch[0];
		return x;
	}
}

int kth(int s)
{
	int x=root;
	while (1)
	{
		if (tree[tree[x].ch[0]].size>=s) x=tree[x].ch[0];
		else
		{
			if (tree[tree[x].ch[0]].size+tree[x].cnt<s)
			{
				s-=tree[tree[x].ch[0]].size+tree[x].cnt;
				x=tree[x].ch[1];
			}
			else return x;
		}
	}
}

int count(int key)
{
	int k=last(key);
	splay(k,0);
	return tree[tree[root].ch[0]].size+tree[k].cnt;
}

void insert(int key)
{
	int k,kk;
	k=last(key);
	splay(k,0);
	kk=next(key);
	splay(kk,0);
	splay(k,kk);
	if (tree[k].ch[1]!=0)
	{
		tree[tree[k].ch[1]].cnt++;
		splay(tree[k].ch[1],0);
	}
	else
	{
		tree[k].ch[1]=++tot;
		tree[tot].key=key;
		tree[tot].cnt=1;
		tree[tot].fa=k;
		tree[tot].size=1;
		splay(k,0);
	}
}

void Delete(int key)
{
	int k,kk;
	k=last(key);
	splay(k,0);
	kk=next(key);
	splay(kk,0);
	splay(k,kk);
	
	tree[tree[k].ch[1]].cnt--;
	if (tree[tree[k].ch[1]].cnt==0)
	{
		tree[k].ch[1]=0;
		splay(k,0);
	}
	else
	{
		splay(tree[k].ch[1],0);
	}
}

int main()
{
	freopen("read.in","r",stdin);
	freopen("write.out","w",stdout);
	scanf("%d",&n);
	tree[1].key=-1;tree[1].cnt=1;tree[1].size=2;tree[1].ch[1]=2;
	tree[2].key=1000000001;tree[2].cnt=1;tree[2].fa=1;tree[2].size=1;
	tot=2;root=1;
	for (i=1;i<=n;i++)
	{
		scanf("%d%d",&type,&x);
		if (type==0)
		{
			insert(x);
		}
		if (type==1)
		{
			Delete(x);
		}
		if (type==2)
		{

			printf("%d
",tree[kth(x+1)].key);
		}
		if (type==3)
		{

			printf("%d
",count(x)-1);
		}
		if (type==4)
		{

			ans=last(x);
			if (ans>2)
			printf("%d
",tree[ans].key);
			else
			printf("-1
");
		}
		if (type==5)
		{

			ans=next(x);
			if (ans>2)
			printf("%d
",tree[ans].key);
			else
			printf("-1
");
		}
	}
}

维护序列

其中维护序列这道题应该是集大成者。

这道题有插入区间，删除区间，区间修改赋值，区间翻转，区间求和，求最大字段和六个操作。还需要建一个回收站存被删除的节点

改了我一晚上

极大地锻炼了我的意志力和耐心（其实哪道splay的题我没有调一晚上）

码完这道题，我的splay就小成了

这篇笔记也就可以告一段落了

让我们欣赏一下这美妙的代码吧

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct qy
{
	int ch[2],fa,key,size,sum,ma,mal,mar,sam,rev;
};

int n,m,i,j,k,TAGNONE,root,x,s,num,ggg;
int a[500010],bin[500100],list[500005];
qy tree[500010];
char str[20];

int get(int x)
{
	if (tree[tree[x].fa].ch[0]==x) return 0;
	else return 1;
}

void update(int x)
{
	int ch0=tree[x].ch[0]; int ch1=tree[x].ch[1];
	tree[x].size=tree[ch0].size+tree[ch1].size+1;
	tree[x].sum=tree[ch0].sum+tree[ch1].sum+tree[x].key;
	tree[x].mal=max(tree[ch0].mal,tree[ch0].sum+tree[x].key+tree[ch1].mal);
	tree[x].mar=max(tree[ch1].mar,tree[ch1].sum+tree[x].key+tree[ch0].mar);
	tree[x].ma=max(max(tree[ch0].ma,tree[ch1].ma),tree[ch0].mar+tree[x].key+tree[ch1].mal);
}

void cha_rev(int x)
{
	swap(tree[x].ch[0],tree[x].ch[1]);
	swap(tree[x].mal,tree[x].mar);
	tree[x].rev^=1;
}

void cha_sam(int x,int key)
{
	tree[x].key=key;
	tree[x].sum=key*tree[x].size;
	tree[x].ma=max(tree[x].sum,key);
	tree[x].mal=max(tree[x].sum,0);
	tree[x].mar=max(tree[x].sum,0);
	tree[x].sam=key;
}

void pushdown(int x)
{
	if (tree[x].rev)
	{
		if (tree[x].ch[0]) cha_rev(tree[x].ch[0]);
		if (tree[x].ch[1]) cha_rev(tree[x].ch[1]);
		tree[x].rev=0;
	}
	if (tree[x].sam!=TAGNONE)
	{
		if (tree[x].ch[0]) cha_sam(tree[x].ch[0],tree[x].sam);
		if (tree[x].ch[1]) cha_sam(tree[x].ch[1],tree[x].sam);
		tree[x].sam=TAGNONE;
	}
}

int newnode()
{
	return bin[bin[0]--];
}

void rotate(int x)
{
	int y=tree[x].fa;
	int z=tree[y].fa;
	int k=get(x);
	int kk=get(y);
	if (z) 
	tree[z].ch[kk]=x;
	tree[x].fa=z;
	tree[y].ch[k]=tree[x].ch[k^1];
	if (tree[x].ch[k^1])
	tree[tree[x].ch[k^1]].fa=y;
	tree[x].ch[k^1]=y;
	tree[y].fa=x;
	update(y);
	update(x);
}

void remove(int x,int y)
{
	list[0]=0;
	while (x!=y)
	{
		list[++list[0]]=x;
		x=tree[x].fa;
	}
	for (int i=list[0];i>=1;i--)
		pushdown(list[i]);
}

void splay(int x,int goal)
{
	remove(x,goal);
	while (tree[x].fa!=goal)
	{
		int y=tree[x].fa;
		if (tree[y].fa!=goal)
		{
			if (get(x)==get(y)) rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if (goal==0) root=x;
}

int build(int l,int r,int fa)
{
	if (l>r) return 0;
	int mid=(l+r)/2;
	int x=newnode();
	tree[x].fa=fa;
	tree[x].key=a[mid];
	tree[x].rev=0;
	tree[x].sam=TAGNONE;
	tree[x].ch[0]=build(l,mid-1,x);
	tree[x].ch[1]=build(mid+1,r,x);
	update(x);
	return x;
}

void find(int s)
{
	int x=root;
	while (s!=0)
	{
		pushdown(x);
		if (tree[tree[x].ch[0]].size+1<s)
		{
			s-=tree[tree[x].ch[0]].size+1;
			x=tree[x].ch[1];
		}
		else
		{
			if (tree[tree[x].ch[0]].size+1==s)
				s-=tree[tree[x].ch[0]].size+1;
			else
				x=tree[x].ch[0];
		}
	}
	splay(x,0);
}

void insert(int x,int s)
{
	int k,kk;
	find(x+1);
	k=root;
	find(x+2);
	kk=root;
	splay(k,kk);
	tree[k].ch[1]=build(1,s,k);
	update(k);
	update(kk);
}

void recycle(int x)
{
	if (tree[x].ch[0]) recycle(tree[x].ch[0]);
	if (tree[x].ch[1]) recycle(tree[x].ch[1]);
	bin[++bin[0]]=x;
}

void Delete(int x,int s)
{
	int k,kk;
	find(x);
	k=root;
	find(x+s+1);
	kk=root;
	splay(k,kk);
	recycle(tree[k].ch[1]);
	tree[k].ch[1]=0;
	update(k);
	update(kk);
}

void makesame(int x,int s,int num)
{
	int k,kk;
	find(x);
	k=root;
	find(x+s+1);
	kk=root;
	splay(k,kk);
	cha_sam(tree[k].ch[1],num);
	update(k);
	update(kk);
}

void reverse(int x,int s)
{
	int k,kk;
	find(x);
	k=root;
	find(x+s+1);
	kk=root;
	splay(k,kk);
	cha_rev(tree[k].ch[1]);
	update(k);
	update(kk);
}

int query(int x,int s)
{
	int k,kk;
	find(x);
	k=root;
	find(x+s+1);
	kk=root;
	splay(k,kk);
	return tree[tree[k].ch[1]].sum;
}

int main()
{
	freopen("read.in","r",stdin);
	freopen("write.out","w",stdout);
	TAGNONE=-2000;
	for (i=1;i<=500005;i++)
	bin[++bin[0]]=500005-i+1;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	tree[0].ma=-200000000;
	a[0]=a[n+1]=-200000000;
	root=build(0,n+1,0);
	for (i=1;i<=m;i++)
	{
		scanf("%s",str+1);
		if (str[1]=='I')
		{
			scanf("%d%d",&x,&s);
			for (j=1;j<=s;j++)
			scanf("%d",&a[j]);
			insert(x,s);
		}
		if (str[1]=='D')
		{
			scanf("%d%d",&x,&s);
			Delete(x,s);
		}
		if ((str[1]=='M')&&(str[3]=='K'))
		{
			scanf("%d%d%d",&x,&s,&num);
			makesame(x,s,num);
		}
		if (str[1]=='R')
		{
			scanf("%d%d",&x,&s);
			reverse(x,s);
		}
		if (str[1]=='G')
		{
			scanf("%d%d",&x,&s);
			printf("%d
",query(x,s));
		}
		if ((str[1]=='M')&&(str[3]=='X'))
		{
			printf("%d
",tree[root].ma);
		}
	}
	return 0;
}

最后，我想用一句话来结束这篇笔记：

攀登顶峰，这种奋斗的本身就足以充实人的心。人们必须相信，垒山不止就是幸福。

​ ————-——–加缪

2019.7.4晚