首页 Notes

# Splay 复习笔记

# Part 1. Balanced Tree

​ 就是讲，一棵带权二叉树，对于每个节点 xx ，左子树的权值都比 valxval_x 的要小，右子树的权值比 valxval_x 要大。

​ 在上面可以容易的维护出区间第 kk 大，插入删除一个数，求出一个数的排名等操作，由于是课二叉树，每次复杂度是 O(树高)O(\texttt{树高}) 的，所以我们需要用一些数据结构来保证树高为 log⁡\log 层以保证复杂度，splaysplay 就是其中一种

# Part 2. Splay

# rotate：rotate：

​ splaysplay 一个比较核心的操作，大致是把一个点向上旋转。设我们将 xx 旋上去，它的父亲为 yy，yy 的父亲为 zz，考虑我们该怎样翻转。

​ 以 xx 为 yy 的左儿子为例：

​ 为保证二叉平衡树的性质，yy 的权值是比 xx 大的，故翻转后它要成为 xx 的右儿子，而 yy 的左儿子（比 yy 小）将会是 xx 最初的右儿子（比 xx 大，比 yy 小），不难实现代码

1
2
3
4
5
6
inline void rotate (int x) {
    int y = fa[x], z = fa[y], k = get(x);
    ch[y][k] = ch[x][!k]; fa[ch[x][!k]] = y;
    fa[x] = z; if(z) ch[z][ch[z][1] == y] = x; 
	ch[x][!k] = y, fa[y] = x;
}

# SplaySplay

​ 将 xx 一直旋转到根

​ 还是来看 x,y,zx, y, z，若 xx ，yy ，为他们父亲一样性质的儿子，那这三个点会有一条链，这样若先旋 xx ，再旋 yy ，这条链不会消失，故要换个方式来旋

1
2
3
4
5
6
inline void splay (int x){
    int p;
    for (p = fa[x]; p = fa[x], p; rotate(x))
        if (fa[p])  get(x) == get(p) ? rotate(p) : rotate(x);
	rt = x;
}

# Insert

​ 插入一个点，我们肯定要找到一个位置插

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert (int x) {
    if (!rt) {
        val[++tot] = x; cnt[tot] = 1; rt = tot; maintain(rt); return ;
    } 
    int cur = rt, p = 0;
    while (1) {
		if (val[cur] == x) {
            cnt[cur]++;
            maintain(cur); maintain(p);  splay(cur); return ;
        }
       	p = cur; cur = ch[cur][val[cur] < x];
        if (!cur) {
            val[++tot] = x; cnt[tot]++; fa[tot] = p; ch[p][val[p] < x] = tot;
            maintain(tot); maintain(p); splay(tot); return ;
        }
    }
}

# rank

​ 也类似

1
2
3
4
5
6
7
8
9
10
11
inline int rk (int x) {
	int res = 0, cur = rt;
	while (1) {
		if (x < val[cur]) cur = ch[cur][0]
		else {
			res += siz[ch[cur][0]];
			if (k == val[cur]) return splay(x), res + 1;
			res += cnt[cur]; cur = ch[cur][1];
		}
	}
}

# kth

没有感情的贴码机器

1
2
3
4
5
6
7
8
9
10
11
int kth (int k) {
	int cur = rt;
	while (1) {
		if (ch[cur][0] && k <= siz[ch[cur][0]]) cur = ch[cur][0];
		else {
			k -= siz[ch[cur][0]] + cnt[cur];
			if (k <= 0) return splay(cur), val[cur];
			cur = ch[cur][1];
		}
	}
}

# pre/nxt

求前驱后继都差不多，无非是抓住二叉平衡树大小关系的限制，先把一个点旋到根，再找它左儿子中最右的 / 右儿子中最左的。

就不写了。

# delete

删除一个权值，你首先要这个权值所在的点把旋到根，也就是 rkrk 一遍

再分类讨论：

  • 若有多个，删一个
  • 若无儿子，直接清空
  • 若只有一个儿子，把它设为新根
  • 若二子健全，则任选它前驱后继作为新根。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void del (int x){
	rk(x);
	if (cnt[x] > 1) {
		cnt[x]--; maintain(x); return ;
	}
	if (!ls && !rs) {
		clear(rt); rt = 0; return ;
	}
	if (!ls || !rs) {
		int k = (!rs);
		int cur = rt;
		rt = ch[cur][!k];
		fa[rt] = 0;
		clear(rt); return ;
	}
	int cur = rt;
	int k = nxt();
	fa[ch[cur][0]] = k;
	ch[k][0] = ch[cur][0]; clear(cur);
	maintain(rt);
}

# Part 3. Application

​ 为啥一个维护二叉平衡树的 datastructure\texttt{data structure} 能够处理序列问题呢？

​ 考虑二叉平衡树中序遍历，若你赋一个排列发现怎么旋都不会变，于是你可以用树上的点当作序列上一个位置（不是数字）。

​ 对区间操作你可以看作把区间左端点 - 1 ，旋到根，区间右端点旋成它的右儿子，这样根的 右儿子的 左子树就是你要操作的区间位置了。

​ 考虑一切好玩的东西都能丢到树上，十有八九能变成一个更好玩的东西，这就是 LinkCutTree\texttt{Link Cut Tree} 的前置部分了。