splay总结（个人笔记）
柒葉灬
2019-02-10 16:50:04
# splay总结
------
$splay$ 本质上是一棵平衡树，
但是用上了$splay$ 算法之后他可以使深度接近$log$
核心函数有下面两个：
1. 翻转节点$x$，$rotate$
2. 把节点$x$变成$goal$的儿子，$splay$
-----
### 代码：
```cpp
int rt,tot,val[maxn],fa[maxn],son[maxn][2],sz[maxn];
void up(int x){
sz[x]=sz[son[x][0]]+sz[son[x][1]]+1;
}
void rotate(int x){
int y=fa[x];
int z=fa[y];
int k=(son[y][1]==x);
son[z][(son[z][1]==y)]=x;
fa[x]=z;
son[y][k]=son[x][k^1];
fa[son[x][k^1]]=y;
son[x][k^1]=y;
fa[y]=x;
up(y);up(x);
}
void splay(int x,int goal){
while(fa[x]!=goal){
int y=fa[x];
int z=fa[y];
if(z!=goal)
(son[z][1]==y)^(son[y][1]==x)?rotate(x):rotate(y);
rotate(x);
}
if(goal==0)rt=x;
}
```
---------
### 插入操作 1：
（注意，这里的插入操作是没有重复元素的情况）
```cpp
void insert(int x){
int u=rt,f=0;
while(u){
f=u;
u=son[u][x>val[u]];
}
u=++tot;
fa[tot]=f;
son[f][x>val[f]]=tot;
val[tot]=x;
sz[tot]=1;
splay(tot,0);
}
```
-------
### 插入操作 2：
但是往往插入的时候不是按照权值来插入，而是按照编号
这时候就用下列的方法即可。
```cpp
void insert(int x){
val[++tot]=x;
fa[tot]=tot-1;
son[tot-1][1]=tot;
sz[tot]=1;
splay(tot,0);
}
```
------------
### 查找前驱和后继
（$0$ 表示找前驱，$1$ 表示找后继）
```cpp
int Next(int x,int type){
splay(x,0);
if(!son[rt][type])return -1;
int u=son[rt][type];
while(son[u][type^1])
u=son[u][type^1];
}
```
------------
### 查找第$K$大元素
```cpp
int find(int K){
int u=rt;
while(true){
if(sz[son[u][0]]>=K)u=son[u][0];
else if(sz[son[u][0]]+1==K)return u;
else K-=sz[son[u][0]]+1,u=son[u][1];
}
}
```
----------
### 删除节点操作
```cpp
void del(int x){
splay(x,0);
if(!son[x][0]||!son[x][1]){
int tmp=(son[x][0]|son[x][1]);
fa[tmp]=0;
rt=tmp;
return;
}
int u=Next(rt,1);
son[u][0]=son[rt][0];
fa[son[rt][0]]=u;
rt=son[rt][1];
fa[son[rt][1]]=0;
splay(u,0);
}
```
-----------------------
## 技巧1. 区间修改操作
在$splay$树中加两个虚点，一个头一个尾。
（保证每一个点都有前驱和后继）
比如说现在需要修改 $ [l,r] $ 这个区间，
#### 代码：
```cpp
void update(int l,int r){
int lx=find(l);
int rx=find(r+2);
splay(lx,0);
splay(rx,lx);
change(son[rx][0]);
}
```
因为一开始在头有一个虚点，所以修改的区间应该是 $[l+1,r+1]$
找到$l+1$的前驱$lx$ -> $find(l)$
以及$r+1$的后继$rx$ -> $find(r+2)$
那么$son[rx][0]$就是我们要修改的区间了。
------------
## 技巧2. 当做线段树使用
$splay$ 可以当做线段树一样维护一个区间的信息
比如说区间求和，最大连续和之类的。
详细见 [splay专题 I](https://vjudge.net/contest/282670#problem/I)
-------------
## 使用细节（重点！！）
一定要尽量用$splay$操作，
不能出现找到一个点之后不$splay$的情况
否则很有可能被卡 T 掉。
$splay$的复杂度是均摊的，是有了$splay$操作才能均摊，
否则复杂度玄学。（出题人可以卡）
详细见[splay专题 J](https://vjudge.net/contest/282670#problem/J)
-----
注意那种修改操作，打$lazy$标记的那种
一定是先修改节点信息再打标记
#### 一定注意不能在$down$的时候才修改！！！
2019、10、27、 update：
# Query完之后要splay一下最后一个访问的节点！！！
--------