prologue

快 csps 了还什么也不会的一条费鱼。

下面是分别通过 acwing y总和樱雪喵学到的splay。

introduction

首先来了解一下二叉搜索树。二叉搜索树是一种二叉树的树形数据结构，其定义如下：

空树是二叉搜索树。
若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
二叉搜索树的左右子树均为二叉搜索树。

下面是我画出来的一棵二叉搜索树，很显然是满足上述性质的（注意，图上的点都是表示点权）。

插入节点

我们如果要插入一个节点，应该遵循上面的规则，这样才能保证这个二叉搜索树的结构是一直保持的：

如果比当前节点的权值大，则向这个节点的右子树遍历。直到叶子节点然后停止，插入该值。
如果比当前节点的权值小，则向这个节点的左子树遍历。直到叶子节点然后停止，插入该值。
如果和当前节点的权值相同，则可以考虑两种方案：
- 直接在这个节点的下面进行连接。
- 给这个权值的节点开一个维度 cnt，用来统计这个权值的个数。

从理论与结构来说，第一种明显是荒谬之谈，但是第一种往往在实际过程中会比第二种少很多的情况特判，操作起来上手舒服。（或许这就是为什么大部分学校把信息学归为工科的原因？）

删除节点

我们删除节点的操作往往会比较麻烦：

如果这个节点没有子树，则我们可以直接删除。
如果只有一个儿子，直接将这个儿子和它的父节点相连，然后删除这个点。（图解）
如果有两个儿子，那么我们删除的过程就会变得比较麻烦。（下面为重建的新图）
- 删除 4 号节点。我们首先先将与 4 相连的边都删掉
- 然后我们用一边的儿子（任意都可，看你习惯，我来左边）与原来的父节点相连。
- 然后我们再按照搜索二叉树的原则，把右儿子给连接上。（图丑轻喷）

这里我们就成功的删除了 4 号节点，并且同时维护了搜索二叉树的性质。

我们对于一个节点的查询是和这个搜索二叉树的树高有关系的。

但是我们其实可以很轻松的构造一种方案，让这个效率降成 \(O(n)\) 了，就是从根节点开始不断加比它大的数，这样子我们的树高就是点的个数，我们的效率也就低了下来。

为了让我们的时间复杂度有保证，我们就诞生了平衡树这一种数据结构。通过左旋（zag）和右旋（zig）来维护搜索二叉树的树高一直为 \(log_2 n\) 的。、

splay

zag & zig

首先我们得介绍清楚 zig 和 zag 的实现原理，否则后期难以进行。下面是摘自 oiwiki 上的图片。
左边通过右旋得到了右边，右边通过左旋得到了左边。

下面是对于左右旋的一个略详解：

右旋：将 \(A\) 的左孩子 \(B\) 向左上旋转，代替 \(A\) 成为根节点，将 \(A\) 结点向右下旋转成为 \(B\) 的右子树的根结点，\(B\) 的原来的右子树变为 \(A\) 的左子树。

左旋则是右旋的镜像操作。

（想了想还是把代码放在这里吧）

由于我们上面的左旋右旋都只和 x 是父亲的哪个儿子进行的方向进行判断。造作完成后，我们要更新节点的 size 信息。

#define ll int

inline void rotate(ll x)
{
	ll y = fa(x), z = fa(y), c = get(x); // x的爹在哪个方向
	if(tr[x].s[c ^ 1]) fa(tr[x].s[c^1]) = y // 把 x 相反方向的儿子接在y上，可以根据图解来联系理解。
	tr[y].s[c] = tr[x].s[c ^ 1], tr[x].s[c ^ 1] = y, fa(y) = x, fa(x) = z;
	if(z) tr[z].s[y == tr[z].s[1]] = x;
	maintain(y), maintain(x);
}

破坏平衡的几个形式

LL型

原因：左子树的左子树过长破坏平衡。解决方案：右旋 zig。

RR型

原因：右子树的右子树过长破坏平衡性。解决方案：左旋 zag。

L-R型

原因：左子树的右子树过长导致破坏平衡性。解决方案：左右旋 zag-zig。

细说：先将左子树的右子树，通过左旋，变成左子树的左子树，即 LL 型，然后再右旋，达到平衡。

R-L型

原因：右子树的左子树过长导致破坏平衡性。解决方案：右左旋 zig-
zag。

细说：先将右子树的左子树，通过右旋，变成了右子树的右子树，即 RR 型 然后再左旋，达到平衡。

splay操作

我们的 splay 操作就是要将上面几种方式给变成一个平衡的结构，实际上 splay 的代码实现很短。

#define ll int 
#define rl register ll 

inline void splay(ll x)
{
	for(rl f = fa(x); f = fa(x), f; rotate(x))
		if(fa(f)) rotate(get(f) == get(x) ? f : x);
	root = x;
}

为了保证 splay 的时间复杂度，我们规定每次最后访问到的节点是 x，都要把 x Splay 到根上。

时间复杂度分析

分析什么分析啊，计算机是工科！（just kidding，~~实际上是菜鱼不会分析~~）
这里贴一个复杂度证明想了解的神仙可以自行学习。知道这个复杂度是 \(logn\) 的就行了。

应用

之后就是一些查询插入修改访问之类的了，和二叉搜索树基本上没有多大关联了。

这里一个操作一个操作的展开。

插入

其实本质的思路和二叉搜索树没有多大的区别，主要是最后要 splay 一下维护我们平衡树的结构。

#define ll int 
#define rl register ll 

inline void insert(ll key)
{
	ll now = rt,  f = 0;
	while(now) f = now, now = tr[now].s[key>tr[now].key];
	now = newnode(key), fa(now) = f, tr[f].s[key>tr[now].key] = now, splay(now);
}

删除

前面已经说过了二叉搜索树是怎么样实现删除操作的，下面直接放代码了。

inline void delete(ll key)
{
	ll now = root, p = 0;
	while(tr[now].key != key && now) p = now, now = tr[now].s[key>tr[now].key]; // 找到要删除的节点
	if(!now) { splay(p); return ; }
	splay(now), ll cur = ls(now);
	if(!cur) { rt = rs(now), fa(rs(now))=0, clear(now); return ; } 
	while(rs(cur)) cur = rs(cur);
	rs(cur) = rs(now), fa(rs(now)) = cur, fa(ls(now)) = 0, clear(now); // 把右儿子接在（左子树的最大权值）下面
	maintain(cur), splay(cur);
}

查询 x 的排名

从根节点开始，根据左子树的 \(size\) 判断我们查询的 \(x\) 在哪棵子树里面；因为一个平衡树里可能有一堆权值是 \(x\) 的点，这里我们本质上是要找到严格小于 \(x\) 的点数 + 1。

每次都往右子树走，左边的子树就给答案贡献了 \(size_ls(now) + 1\) 个比 \(x\) 要小的数。

#define ll long long 
#define rl register ll 

inline ll rank(ll key)
{
	ll res = 1, now = root, p;
	while(now)
		if(p = now, tr[now].key < key) res += tr[ls(now)].size + 1, now = rs(now);
		else now = ls(now);
	
	return splay(p), res;
}

注意，这里虽然只在树上跑点，没有改变数的结构，但任然要 splay（把splay这个操作当成施法后摇就行了）

查询排名为 k 的数

同理，根据子树 \(size\) 直接判断排名为 \(k\) 的数走哪一边。

#define ll long long 
#define rl register ll 

inline void get_key_by_rank(ll rk)
{
	ll now = root;
	while(now) 
	{
		ll sz = tr[ls(now)].size + 1;
		if(sz > rk) now = ls(now);
		else if(sz == rk) break;
		else if(sz < rk) rk -= sz, now = rs(now);
	}
	return splay(now), tr[now].key;
}

查询 x 的前驱

从根节点开始往下走，如果当前点大于等于 x，那么这个的前驱就一定在左子树，我们就往左走；否则，前驱可能在这个点或者在右子树，这个时候我们先用这个节点更新答案，然后再去这个节点的右子树继续找。

#define ll long long
#define rl register ll 

inline ll pre(ll key)
{
	ll now = root, ans = 0, p;
	while(now)
		if(p = now, tr[now].key >= key) now = ls(now);
		else ans = tr[now].key, now = rs(now);
	return splay(p), ans;
}

查询 x 的后继

把前去操作倒过来就好了。

#define ll long long
#define rl register ll

inline ll  suf(ll key)
{
	ll now = root, ans = 0, p;
	while(now)
		if(p = now, tr[now].key <= key) now = rs(now);
		else ans = tr[now].key, now = ls(now);
	return splay(p), ans;
}

完整版的板子

点击查看代码

一些上面操作的复合版本

这里的 \(splay(a, b)\) 是指的将 a 一路翻转到 b 的下面。

inline void splay(ll x, ll y)
{
	for(rl f=fa(x);f=fa(x), f != y; rotate(x))
		if(fa(f) != y) rotate(get(f) == get(x) ? f : x);
	if(!y) root = x;
}

将一个序列插入到 y 的后面

找到 y 的后继 z。
将 y 旋转到根节点。splay(y, 0);
将 z 转到 y 的下面。 splay(z, y);
将序列加在 z 的左子树下。

删除 \([l, r]\) 这一段

找到 l 的前驱 a，找到 r 的后继 b。
将 a 转到根，将 b 转到根的下面。
此时，b 的左子树就是 \([l, r]\) 就是我们要删除的区间。直接将 b 的左子树清空行了。

find函数

找到下标为 x 的点，原理和二叉搜索树的找排名为 k 的函数相同。注意！我们因为在进行递归操作的时候要一边去找然后一边区 pushdown。同时因为我们会有一个虚点所以最后找到的排名是实际的下标 + 1。

inline ll find(ll x)
{
	ll now = root, x ++ ;
	while(now)
	{
		pushdonw(now); ll sz = tr[ls(now)].size + 1;
		if(sz == x) break;
		else if(sz > x) now = ls(now);
		else now = rs(now), x -= sz;
	}
	return now;
}

reverse

inline void reverse(ll l, ll r)
{
	ll x = find(l - 1); splay(x, 0);
	ll y = find(r + 1); splay(y, x);
	tr[ls(y)].lz ^= 1;
}

build

inline void build()
{
	root = newnode(0); ll now = root;
	for(rl i=1; i <= n + 1; ++ i, now = rs(now)) tr[now].size = n + 3 - i, rs(now) = newnode(a[i]), fa(rs(now)) = now;
}

输出

我们的平衡树一直就是维护的一个中序遍历，所以只需要中序遍历就能够输出出来原序列。

inline void write(ll now)
{
	pushdown(now);
	if(ls(now)) write(ls(now));
	if(tr[now].key) cout << tr[now].key << endl;
	if(rs(now)) write(rs(now));
}

526互联