首页 > 代码库 > 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总结