杂

啊淦，，不知道咕了多久了已经 对没错现在还要咕，现在才想起来写，忘干净了都快，qvq，一看这种代码一大片的就完全提不起劲儿的说

Splay简述&结构

BST -- 二叉查找树，任意左儿子 < 父亲节点 ， 任意右儿子 > 父亲节点（对每个节点都符合

Splay -- 是一种BST，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链，它由 Daniel Sleator 和 Robert Tarjan 发明，Tarjan np！！

维护的信息

因为存在 左子树任意节点的值 < 根节点的值 < 右子树任意节点的值 的性质，我们能从这棵树上查找某个值

Various operations

the basic

• \(maintain(p)\) ： 改变节点位置后更新节点的\(size\)
• \(get(p)\) ： 判断某节点为左儿子还是右儿子
• \(clear(p)\) ： 销毁节点

void maintain(int p) { sz[p] = sz[o[p][0]] + sz[o[p][1]]; }
bool get(int p) { return o[f[p]][1] = p; }
void clear(int p) { o[p][0] = o[p][1] = f[p] = v[p] = sz[p] = cnt[p] = 0; }

rotate

旋转操作>>>>

以左图到右图为例，现在要将p节点向上移一个位置，将1-p-fp-3这条链往右移一个位置，2的父亲由右上的p换为左上的fp（旋转之后的结果），，过程中我们要维护这棵树BST的性质，

过程：

1. fp 为 p 的父亲，ffp 为 fp 的父亲，oo 表示 p 为左儿子还是右儿子
2. 让 fp 的儿子 o[fp][oo]变为 2 o[p][oo ^ 1]，让 2 f[o[p][oo ^ 1]] 的父亲变为 fp
3. 让 p 的儿子 o[p][oo ^ 1] 变为 fp ，让 fp 的父亲 f[fp] 变为 p
4. 如果存在 fp 的父亲 ffp（fp不是根节点），让 ffp 的儿子 o[ffp][get[fp]] 变为 p，p 的父亲变为 ffp

? \(\lll-相互-\ggg\)

void rotate(int p) {
	int fp = f[p], ffp = f[fp], oo = get(p);
	o[fp][oo] = o[p][oo ^ 1];
	f[o[p][oo ^ 1]] = fp;
	o[p][oo ^ 1] = fp; 
	f[fp] = p; f[p] = ffp;
	if(ffp) o[ffp][fp == o[ffp][1]] = p;
	maintain(fp); 
	maintain(p);
}

咕着，三天内更完【真香警告】

Splay

原文：https://www.cnblogs.com/moziii/p/13406629.html