splay
其实离听splay也不过一个月的时间，但今天复习的时候真的是忘的一干二净。复习其实是预习后来总结一下（明白要经常复习的重要性）。
参考https://baijiahao.baidu.com/s?id=1613228134219334653&wfr=spider&for=pc
splay维护平衡的方法是不停的将一个点旋转到根来维护平衡，核心操作就是旋转。
旋转时分为两种形式：1.三点一线就先旋转父亲，再旋转x。2.不是三点一线就一直旋转x 。
代码很巧妙（程序语音的魅力），先贴出来结合着分析。
void rotate(int x){//旋转 int old=f[x],oldf=f[old],which=get(x);//old是x爸爸，oldf是爷爷，which是连向父亲边的方向 ch[old][which]=ch[x][which^1];f[ch[old][which]]=old;//右旋：x的右儿子变为old的左儿子；左旋：x的左儿子变为old的右儿子 f[old]=x;ch[x][which^1]=old; f[x]=oldf; if (oldf) ch[oldf][ch[oldf][1]==old]=x; update(old);update(x); }
注意连边的方向，手动模拟一下是最好的。
一直旋转到根再加一个这个就可以了。
void splay(int x) { for (int fa;(fa=f[x]);rotate(x)) if (f[fa]) rotate((get(x)==get(fa)?fa:x));//三点一线就先旋转父亲，再旋转x；不是三点一线就一直旋转x root=x;//把x一直旋转到根 }
以上就是splay的核心操作。
还有一些基础操作，很好理解，所以就直接贴了
插入
void insert(int v){//插入 if (root==0) {sz++;ch[sz][0]=ch[sz][1]=f[sz]=0;key[sz]=v;cnt[sz]=1;size[sz]=1;root=sz;return;} int now=root,fa=0; while (1){ if (key[now]==v){ cnt[now]++;update(now);update(fa);splay(now);break;//记得要splay一下 } fa=now; now=ch[now][key[now]<v]; if (now==0){//找到叶子节点 sz++; ch[sz][0]=ch[sz][1]=0;key[sz]=v;size[sz]=1; cnt[sz]=1;f[sz]=fa;ch[fa][key[fa]<v]=sz; update(fa); splay(sz);//记得要splay一下 break; } } }
查询x的排名
int find(int v){ int ans=0,now=root; while (1){ if (v<key[now]) now=ch[now][0]; else{ ans+=(ch[now][0]?size[ch[now][0]]:0); if (v==key[now]) {splay(now);return ans+1;} ans+=cnt[now]; now=ch[now][1]; } } }
找到排名为x的点
int findx(int x){ int now=root; while (1){ if (ch[now][0]&&x<=size[ch[now][0]]) now=ch[now][0]; else{ int temp=(ch[now][0]?size[ch[now][0]]:0)+cnt[now]; if (x<=temp) return key[now]; x-=temp;now=ch[now][1]; } } }
前驱
int pre(){ int now=ch[root][0];//先往左走一步，前驱是左子树的最大 while (ch[now][1]) now=ch[now][1]; return now; }
后继
int next(){//先往右走一步，后继是右子树的最小 int now=ch[root][1]; while (ch[now][0]) now=ch[now][0]; return now; }
删除
删除要稍微复杂一点，但同样的，把这个点旋转到根，然后有三种情况：
1.改点有重复个数，那么就把个数-1就行了。
2.有一个儿子，那么如果有左儿子就让左儿子做根，有右儿子就让右儿子做根。
3.有两个儿子，就让前驱（即左儿子）做根，然后直接将右儿子变成原来左儿子（现在的根）的右儿子，再清理掉老根就好了。
void del(int x){//删除 find(x);//find(x)后x位于根节点 if (cnt[root]>1) {cnt[root]--;update(root);return;}//有重复的个数 if (!ch[root][0]&&!ch[root][1]) {clear(root);root=0;return;} //一个儿子 if (!ch[root][0]){int oldroot=root;root=ch[root][1];f[root]=0;clear(oldroot);return;} else if (!ch[root][1]){int oldroot=root;root=ch[root][0];f[root]=0;clear(oldroot);return;} int leftbig=pre(),oldroot=root;//2个儿子 splay(leftbig);//让前驱做根 f[ch[oldroot][1]]=root; ch[root][1]=ch[oldroot][1]; clear(oldroot); update(root); return; }
Treap就下次再整理~