首页 > 代码库 > splay总结
splay总结
以此文纪念人生首次竞赛大选
这里主要讲一讲splay的区间操作，我讲的是指针实现，程序的效率可能比较低，更偏重代码的可读可写性，语言风格不是很优美有效，不喜勿喷
零、初始化结构体
1）这里主要是初始化结构体，记得先生成一个null节点指针，代表一切未使用的、未开发的节点，root也先赋值为null
2）结构体成员：有几个指针，如父亲（没有也可以，只不过令splay失去一些平衡树的功能），左右儿子，这里用数组记录，下标为0,1，方便我们操作
有几个需要维护的域，如size，子树和根的大小（包括重复节点），mul，重复节点的计数器，rev，区间翻转标记，一层一层地传，addnum，区间加的标记，cov，区间覆盖标记
3）结构体函数：可以自己写一个构造函数，可以声明后在结构体外写，就可以用null指针了，但最好是在结构体外写一个newnode，这样更清晰且更灵活
4）下传函数（relax/pushdown）：
DEBUG：这里注意每次下传rev时，要马上实现交换左右儿子
DEBUG：这里注意所有的，如max域和sum域也要进行区间加操作
主要实现了区间加、区间覆盖、区间翻转的标记的下传
DEBUG：记得从上到下pushdown
5）更新函数（pushup/update）：
根据需要看max域从儿子传上来挑最大，size域加儿子的size和自己的mul，不考虑重复时就用1代替
DEBUG：记得从下到上pushup
一、插入/构造
DEBUG：一下所有的涉及改动的操作记得用址传，不然会出大事哦
1）区间插入，先说进阶的，我们直接对构造一棵平衡树后，将所需区间伸展至根节点右儿子的左儿子处，将构造号的树塞到那里
DEBUG：这里注意塞完树以后记得更新根节点右儿子和根节点的维护域
2）单点插入，和区间一样，伸展所需位置，插入即可
DEBUG：一样滴，这里注意塞完树以后记得更新根节点右儿子和根节点的维护域
（似乎最后将插入的区间做一次splay可以提高效率）
二、删除
主要讲讲区间吧，先把区间伸展到指定位置，我是用递归实现整颗子树的删除的，先递归非空左右儿子，后用系统关键字delete删除当前指针
DEBUG：这里一样要更新有关节点，即pushup
三、旋转
这就不需要多说，平衡树的基础知识
我的函数是指定当前节点，将其对父亲旋转
DEBUG：注意下操作顺序
先提取出父亲的指针，再把当前节点接到父亲的位置
此后把当前和节点异侧的儿子接到父亲连当前节点的位置
之后把父亲接到这个儿子的位置
记得更新一下
四、splay函数/伸展操作
简化一下，主要分了三种情况
第一，当前节点的爷爷是目标节点，直接旋转当前节点
否则
第二，当前节点和父亲不在同侧，旋转当前节点两次
第三，当前节点和父亲在同侧，就先旋转父亲，再旋转当前节点
DEBUG：在函数结尾记得对当前节点进行更新操作，因为旋转函数的更新可能不完全
五、求第k个
这个没什么好说的，我是用循环实现的，非递归
可能此后还有一些进阶操作，这里就不提及了，那不是总结可以穷尽的
最后放个板
#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define mid ((x>>1)+(y>>1)+(x&y&1))using namespace std;const int N = 1e4+10;const int inf = ~0U>>1;struct nt{ nt*ch[2],*p; int k,size; int add;bool rev; bool d(){ return this==p->ch[1]; } void setc(nt*c,int d){ ch[d]=c; c->p=this; } void addIt(int ad){ k+=ad; add+=ad; } void revIt(){ rev^=1; swap(ch[0],ch[1]); } void pu(){ size=1+ch[0]->size+ch[1]->size; } void relax(){ if(rev) ch[0]->revIt(), ch[1]->revIt(), rev=0; if(add) ch[0]->addIt(add), ch[1]->addIt(add), add=0; }};nt*null=new nt();nt*root=null;int a[N];nt*make(nt*p,int k){ nt*now=new nt(); now->size=1; now->k=k; now->p=p; now->ch[0]=now->ch[1]=null; return now;}void rot(nt*&o){ nt*p=o->p; p->relax(); o->relax(); bool d=o->d(); p->p->setc(o,p->d()); p->setc(o->ch[!d],d); o->setc(p,!d); p->pu();o->pu(); if(p==root)root=o;}void splay(nt*o,nt*p){ while(o->p!=p) if(o->p->p==p) rot(o); else o->d()^o->p->d()?(rot(o),rot(o)):(rot(o->p),rot(o)); o->pu();}nt*build(int x,int y){ if(x>y)return null; nt*o=make(o,a[mid]); o->setc(build(x,mid-1),0); o->setc(build(mid+1,y),1); o->pu(); return o;}void del(nt*&o){ if(o->ch[0]!=null)del(o->ch[0]); if(o->ch[1]!=null)del(o->ch[1]); delete o;}nt*kth(int k){ for(nt*o;;){ o->relax(); if(k<=o->ch[0]->size) o=o->ch[0]; else{ k-=o->ch[0]->size+1; if(!k)return o; o=o->ch[1]; } }}int main(){ int n; /* *a=read(1~n) */ root=build(0,n+1); root->p=null; /* insert l,r? *a=read(1~r) splay(kth(l+1),null) splay(kth(l+2),root) root->ch[1]->setc(build(1,r),0) root->ch[1]->pu() root->pu() */ return 0;}
完结，撒花~~~
splay总结