Splay 与 Link-Cut Tree 学习笔记

Splay 学习笔记

Splay 简介

个人感觉 Splay 没有 FHQ-Treap 用着舒服，代码也长很多，但是为了学 LCT，不得不学一下 Splay。

Splay（伸展树）是一种二叉查找树，通过不断地将节点旋转到根节点，使得整棵树仍满足二叉查找树的性质，并且能够保持平衡而不退化成链，由 Daniel Sleator 和 Robert Tarjan 发明。

Splay 结构

Splay 首先是一棵二叉查找树。

Splay 需要维护如下信息：

• \(rt\)：根节点。
• \(sz\)：节点个数。

同时，每个节点需要维护如下信息：

• \(fa\)：父亲节点。
• \({son}_{0/1}\)：左右节点。
• \(val\)：权值。
• \(cnt\)：有几个数。
• \(sz\)：子树大小。

Splay 操作

pushup 操作

pushup 用于更新节点信息。

void pushup(int u) {t[u].sz = t[t[u].son[0]].sz + t[t[u].son[1]].sz + t[u].cnt;}

get 操作

get 用于判断一个节点是它的父亲的哪个儿子。

bool get(int u) {return u == t[t[u].fa].son[1];}

rotate 操作

rotate 用于将一个节点上移一个位置，要满足二叉查找树性质。

有两种旋转：左旋和右旋。这里贺一张 OI Wiki 图片过来：

观察左侧图片到右侧图片的“右旋 \(2\)”过程，进行的操作如下：

• 将 \(2\) 的右儿子变为 \(1\) 的左儿子。
• 将 \(1\) 变为 \(2\) 的右儿子。
• 如果 \(1\) 有父亲，将原来 \(1\) 的位置换成 \(2\)。

容易发现这棵树的中序遍历不变，也就是说依然满足二叉查找树的性质。为了使每个节点维护的信息依然有效，需要依次对 \(1,2\) 进行 pushup 操作。

左旋同理。

void rotate(int u) {
	int f = t[u].fa, p = t[f].fa, id = get(u), idf = get(f);
	t[f].son[id] = t[u].son[id^1];
	if(t[u].son[id^1]) t[t[u].son[id^1]].fa = f;
	t[u].son[id^1] = f;
	t[f].fa = u;
	t[u].fa = p;
	if(p) t[p].son[idf] = u;
	pushup(f);
	pushup(u);
}

splay 操作

splay 用于将一个节点旋转到根，Splay 规定每访问一个节点都要进行这个操作。

分三种情况考虑：节点的父亲是根、节点和父亲的关系与父亲和祖父的关系相同、节点和父亲的关系与父亲和祖父的关系不同。

下面是这三种情况对应的图，为了理解这一操作，建议自行画图模拟一下（我画了一白板莫名爆字迹）：

操作复杂但代码十分简短：

void splay(int u) {
	for(int f=t[u].fa;f=t[u].fa;rotate(u)) {
		if(t[f].fa) rotate(get(u) == get(f) ? f : u);
	}
	rt = u;
}

insert 操作

insert 用于插入一个数。

分几种情况：

• 如果树是空的，新建一个节点插进去即可。
• 否则根据二叉查找树性质找到要插入的位置，如果已经有节点，就把 \(cnt\) 加一然后 pushup，否则新建一个节点插进去。

记得进行 splay 操作。

void insert(int w) {
	int u = rt, f = 0;
	if(!u) {
		u = ++sz;
		t[u].val = w;
		t[u].cnt = 1;
		rt = u;
		pushup(u);
		return;
	}
	while(true) {
		if(t[u].val == w) {
			++t[u].cnt;
			pushup(u);
			pushup(f);
			splay(u);
			break;
		}
		f = u;
		u = t[u].son[t[u].val < w];
		if(!u) {
			u = ++sz;
			t[u].val = w;
			t[u].cnt = 1;
			t[u].fa = f;
			t[f].son[t[f].val < w] = u;
			pushup(u);
			pushup(f);
			splay(u);
			break;
		}
	}
}

rk 操作

rk 用于查询一个数的排名。

根据二叉查找树性质找到对应位置即可，记得记录有多少个数比查询的数小。

int rk(int w) {
	int u = rt, ans = 0;
	while(true) {
		if(w < t[u].val) {
			u = t[u].son[0];
			continue;
		}
		ans += t[t[u].son[0]].sz;
		if(w == t[u].val) {
			splay(u);
			return ans + 1;
		}
		ans += t[u].cnt;
		u = t[u].son[1];
	}
}

kth 操作

kth 用于查询排名为 \(k\) 的数。

根据二叉查找树性质找到对应位置即可。

int kth(int k) {
	int u = rt;
	while(true) {
		if(t[u].son[0] && k <= t[t[u].son[0]].sz) {
			u = t[u].son[0];
			continue;
		}
		k -= t[u].cnt + t[t[u].son[0]].sz;
		if(k <= 0) {
			splay(u);
			return t[u].val;
		}
		u = t[u].son[1];
	}
}

pre 操作和 suc 操作

pre 用于查询根节点的前驱，suc 用于查询根节点的后继。

查询任意数的前驱的做法为先插入，再查根节点前驱，最后删除，后继同理。

根节点的前驱就是左子树内最靠右的节点，后继同理。

int pre() {
	int u = t[rt].son[0];
	if(!u) return 0;
	while(t[u].son[1]) u = t[u].son[1];
	splay(u);
	return u;
}
int suc() {
	int u = t[rt].son[1];
	if(!u) return 0;
	while(t[u].son[0]) u = t[u].son[0];
	splay(u);
	return u;
}

erase 操作

erase 用于删除一个数。

首先将要删的数 splay 到根，然后分几种情况：

• 如果 \(cnt > 1\)，减小一并 pushup 即可。
• 如果既没有左儿子，又没有右儿子，那么直接删掉即可。
• 如果有其中一个儿子，将它放到根并删掉当前节点即可。
• 否则把前驱 splay 到根，并把右子树接到前驱上，然后删掉当前节点即可。

void erase(int w) {
	rk(w);
	if(t[rt].cnt > 1) {
		--t[rt].cnt;
		pushup(rt);
		return;
	}
	if(!t[rt].son[0] && !t[rt].son[1]) {
		t[rt] = Node();
		rt = 0;
		return;
	}
	if(!t[rt].son[0]) {
		int u = rt;
		rt = t[rt].son[1];
		t[rt].fa = 0;
		t[u] = Node();
		return;
	}
	if(!t[rt].son[1]) {
		int u = rt;
		rt = t[rt].son[0];
		t[rt].fa = 0;
		t[u] = Node();
		return;
	}
	int u = rt, x = pre();
	t[t[u].son[1]].fa = x;
	t[x].son[1] = t[u].son[1];
	t[u] = Node();
	pushup(rt);
}

普通平衡树

超长的代码：

// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include 
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 2e5+5;

int n;
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
struct Node {
	int fa, son[2], val, cnt, sz;
	Node() {fa = son[0] = son[1] = val = cnt = sz = 0;}
};
struct Splay {
	Node t[N];
	int rt, sz;
	void pushup(int u) {t[u].sz = t[t[u].son[0]].sz + t[t[u].son[1]].sz + t[u].cnt;}
	bool get(int u) {return u == t[t[u].fa].son[1];}
	void rotate(int u) {
		int f = t[u].fa, p = t[f].fa, id = get(u), idf = get(f);
		t[f].son[id] = t[u].son[id^1];
		if(t[u].son[id^1]) t[t[u].son[id^1]].fa = f;
		t[u].son[id^1] = f;
		t[f].fa = u;
		t[u].fa = p;
		if(p) t[p].son[idf] = u;
		pushup(f);
		pushup(u);
	}
	void splay(int u) {
		for(int f=t[u].fa;f=t[u].fa;rotate(u)) {
			if(t[f].fa) rotate(get(u) == get(f) ? f : u);
		}
		rt = u;
	}
	void insert(int w) {
		int u = rt, f = 0;
		if(!u) {
			u = ++sz;
			t[u].val = w;
			t[u].cnt = 1;
			rt = u;
			pushup(u);
			return;
		}
		while(true) {
			if(t[u].val == w) {
				++t[u].cnt;
				pushup(u);
				pushup(f);
				splay(u);
				break;
			}
			f = u;
			u = t[u].son[t[u].val < w];
			if(!u) {
				u = ++sz;
				t[u].val = w;
				t[u].cnt = 1;
				t[u].fa = f;
				t[f].son[t[f].val < w] = u;
				pushup(u);
				pushup(f);
				splay(u);
				break;
			}
		}
	}
	int rk(int w) {
		int u = rt, ans = 0;
		while(true) {
			if(w < t[u].val) {
				u = t[u].son[0];
				continue;
			}
			ans += t[t[u].son[0]].sz;
			if(w == t[u].val) {
				splay(u);
				return ans + 1;
			}
			ans += t[u].cnt;
			u = t[u].son[1];
		}
	}
	int kth(int k) {
		int u = rt;
		while(true) {
			if(t[u].son[0] && k <= t[t[u].son[0]].sz) {
				u = t[u].son[0];
				continue;
			}
			k -= t[u].cnt + t[t[u].son[0]].sz;
			if(k <= 0) {
				splay(u);
				return t[u].val;
			}
			u = t[u].son[1];
		}
	}
	int pre() {
		int u = t[rt].son[0];
		if(!u) return 0;
		while(t[u].son[1]) u = t[u].son[1];
		splay(u);
		return u;
	}
	int suc() {
		int u = t[rt].son[1];
		if(!u) return 0;
		while(t[u].son[0]) u = t[u].son[0];
		splay(u);
		return u;
	}
	void erase(int w) {
		rk(w);
		if(t[rt].cnt > 1) {
			--t[rt].cnt;
			pushup(rt);
			return;
		}
		if(!t[rt].son[0] && !t[rt].son[1]) {
			t[rt] = Node();
			rt = 0;
			return;
		}
		if(!t[rt].son[0]) {
			int u = rt;
			rt = t[rt].son[1];
			t[rt].fa = 0;
			t[u] = Node();
			return;
		}
		if(!t[rt].son[1]) {
			int u = rt;
			rt = t[rt].son[0];
			t[rt].fa = 0;
			t[u] = Node();
			return;
		}
		int u = rt, x = pre();
		t[t[u].son[1]].fa = x;
		t[x].son[1] = t[u].son[1];
		t[u] = Node();
		pushup(rt);
	}
}splay;

int main() {
	for(scanf("%d", &n);n;n--) {
		int op, x;
		scanf("%d%d", &op, &x);
		if(op == 1) splay.insert(x);
		else if(op == 2) splay.erase(x);
		else if(op == 3) printf("%d\n", splay.rk(x));
		else if(op == 4) printf("%d\n", splay.kth(x));
		else {
			splay.insert(x);
			printf("%d\n", splay.t[op==5?splay.pre():splay.suc()].val);
			splay.erase(x);
		}
	}
	return 0;
}

文艺平衡树

咕咕咕。