$splay$学习总结$QwQ$

省选之前就大概搞了下$splay$,然后因为时间不太够就没写总结了,,,然后太久没用之后现在一回想感觉跟没学过一样了嘤嘤嘤

所以写个简陋的总结,,,肥肠简陋,只适合$gql$复习用,不建议学习用

然后先推荐两篇博客,,,

$orz\ yyb$的博客$QwQ$(我之前就是看这个学的$QwQ$).

$orz\ xzy$学长的博客$QwQ$(这篇总结了支持的操作然后还提供了题单,解释也挺详细的,我真的好爱这种形式的题解$TT$)

概念

$splay$是二叉搜索树的一种,和一般的平衡树不同的是,它对树高是麻油限制的

它基于一个比较贪心的思想?就说查询次数越多的节点离根节点应当是越近的.具体实现就,每次插入或操作一个节点,就把它旋转到根节点

然后$splay$的均摊复杂度大概是$O(log)$的

本来想在这儿写下$splay$呲呲的各种功能,后来想了想,感觉还是写了基操之后结合这些操作港应用会好些,,,所以功能这一帕就放后边儿去了$QwQ$

嗷还有就一般的学习博估计还会写下什么$splay$的旋转原理昂,还有$splay$的结构体$code$什么的,但因为这个是给$gql$复习用,就不写这些了鸭$QwQ$

包括后面的操作什么的也是,因为是个复习向的玩意儿,所以只放代码,原理什么的只有我不太好$get$的才会写下$w$?

操作

定义

int rt,nod_cnt;

struct node{int ch[2],fa,val,cnt,sz;il void pre(ri x,ri fat){ch[0]=ch[1]=0;fa=fat;val=x;cnt=sz=1;}}tr[N];

有时会根据题目性质加一些变量($eg$:$ad$标记,$reverse$标记等$QwQ$),自己灵活变动即可

$umm$为了方便后文,先简要介绍下这些变量的大致定义趴还是$QAQ$

$rt$:根.$nod_cnt$:节点个数.

$ch[2]$:两个子节点.$fa$:父亲节点.$val$:这个点的值.$cnt$:这个值的数目.$sz$:这个点的子树大小

$rotate$

il void pushup(ri x){tr[x].sz=tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz+tr[x].cnt;}
il void rotate(ri x)
{
    ri fa=tr[x].fa,grdfa=tr[fa].fa;bool op1=tr[fa].ch[1]==x,op2=tr[grdfa].ch[1]==fa;
    tr[grdfa].ch[op2]=x;tr[x].fa=grdfa;
    tr[fa].ch[op1]=tr[x].ch[op1^1];tr[tr[x].ch[op1^1]].fa=fa;
    tr[fa].fa=x;tr[x].ch[op1^1]=fa;
    pushup(fa),pushup(x);
}

$splay$

il void splay(ri x,ri goal)
{
    while(tr[x].fa!=goal)
    {
        ri fa=tr[x].fa,grdfa=tr[fa].fa;
        if(grdfa!=goal)(tr[fa].ch[0]==x)^(tr[grdfa].ch[0]==fa)?rotate(x):rotate(fa);
        rotate(x);
    }
    if(!goal)rt=x;
}

$find$

void fd(ri x)
{
    ri nw=rt;if(!nw)return;
    while(tr[nw].ch[x>tr[nw].val] && x!=tr[nw].val)nw=tr[nw].ch[x>tr[nw].val];
    splay(nw,0);
}

$insert$

il void insert(ri x)
{
    ri nw=rt,fa=0;
    while(nw && tr[nw].val!=x)fa=nw,nw=tr[nw].ch[x>tr[nw].val];
    if(nw){++tr[nw].cnt;splay(nw,0);return;}
    nw=++nod_cnt;if(fa)tr[fa].ch[x>tr[fa].val]=nod_cnt;tr[nod_cnt].pre(x,fa);
    splay(nw,0);
}

(一个小$trick$,通常来说,为了防止边界出现什么问题之类的,会在初始的时候$insert$一个$inf$和一个$-inf$

查询前驱后继

int ask_pr(ri x)
{
    fd(x);ri nw=rt;
    if(tr[nw].val<x)return nw;
    nw=tr[nw].ch[0];while(tr[nw].ch[1])nw=tr[nw].ch[1];
    return nw;
}
int ask_lst(ri x)
{
    fd(x);ri nw=rt;
    if(tr[nw].val>x)return nw;
    nw=tr[nw].ch[1];while(tr[nw].ch[0])nw=tr[nw].ch[0];
    return nw;
}

查询第$k$大

int ask_val(ri x)
{
    ri nw=rt;if(tr[nw].sz<x)return false;
    while(gdgs)
    {
        if(x>tr[tr[nw].ch[0]].sz+tr[nw].cnt)
       {
           x-=tr[tr[nw].ch[0]].sz+tr[nw].cnt;
           nw=tr[nw].ch[1];
       }
        else
            if(x<=tr[tr[nw].ch[0]].sz)nw=tr[nw].ch[0];
            else return tr[nw].val;
    }
}

查询排名

int ask_rk(ri x){fd(x);return tr[tr[rt].ch[0]].sz;}

删除

瞎写下原理,,,?

考虑把$x$的前驱旋转到根节点,然后把$x$的后继旋转到根节点的右儿子,由中序遍历就可以知道,根节点的左儿子一定就只有$x$了,直接搞下就好$kk$

void delet(ri x)
{
    ri pr=ask_pr(x),lst=ask_lst(x);
    splay(pr,0);splay(lst,pr);
    if(tr[tr[lst].ch[0]].cnt>1){--tr[tr[lst].ch[0]].cnt;splay(tr[lst].ch[0],0);return;}
    tr[lst].ch[0]=0;
}

应用

先港下,我这儿的应用全部指的对数列中的区间进行操作这样儿,单点的全在前面昂$QwQ$

昂然后如果是对某个数列进行操作,而且每次的操作是给定区间/单点坐标然后要进行修改这样儿,一般是考虑以下标作为节点值,,,?似乎是的趴$QwQ$

还有就,我好像没写得特别全,,,再安利一次$xzy$学长的博客,,,康完他的代码其实就理解的差不多辣我$jio$得.真的写的我觉得挺好的,总结也很全面,代码十分详尽,然后码风我也很喜欢$QwQ$,,,我真的好喜欢这篇博客,,,好对我胃口昂$QAQ$

提取区间

挺简单的?对于$[l,r]$,考虑把$l-1$旋转到根节点,把$r+1$旋转到根节点的右儿子节点,由中序遍历的性质不难得到$[l,r]$就是根节点的右儿子的左节点及其子树

il void extract(ri x,ri y){x=ask_val(x);y=ask_val(y);splay(x,0);splay(y,x);}

插入/删除区间

见下区间交换$QwQ$

区间加/翻转

先把区间提取了,然后跟线段树使得打个$ad$的$lazy\ tag$就好

il void reverse(ri x,ri y)
{
   x=ask_val(x);y=ask_val(y);
   splay(x,0);splay(y,x);
   tr[tr[tr[rt].ch[1]].ch[0]].tg^=1;
}

区间交换

先定义下区间交换,指交换两个相邻的区间昂$QwQ$

总体思路就把后一个区间放到一个子树上,插入到$l-1$和$l$之间就成

具体操作来说,先把$[l_{2},r_{2}]$提取出来,然后把$[l_{2},r_{2}]$记录下来并删了

然后再把$l_{1}-1$挪到根,把$l_{1}$挪到根的右子树,把$[l_{2},r_{2}]$插入到左子树就欧克$QwQ$

然后事实上这个就是插入删除区间的合并版本辽,,,我就懒得再分开写插入删除区间了昂$QwQ$

il void exchange(ri l1,ri r1,ri l2,ri r2)
{
   ri x=ask_val(l2-1),y=ask_val(r2+1);
   splay(x,0);splay(y,x);
   ri tmp=tr[y].ch[0];tr[y].ch[0]=0;
   x=ask_val(l1-1),y=ask_val(l1);
   splay(x,0);splay(y,x);
   tr[y].ch[0]=tmp;tr[tmp].fa=y;
}

区间循环移位

其实就是区间交换来着$hhh$

所以不港辣$QwQ$

合并

这儿合并指的合并俩树,,,

不会,找到了一个学长的$code$,看不懂嘤嘤嘤,,,所以只放下存下,,,等$gql$以后变厉害了会来$upd$的!

il void merge(ri x,ri y)
{
    if(x==y)return;if(size[root[x]]>size[root[y]])swap(x,y);
    F[x]=y;head=tail=0;dui[++tail]=root[x];int u;
    while(head<tail)
    {
        head++;u=dui[head];
        if(tr[u][0])dui[++tail]=tr[u][0];
        if(tr[u][1])dui[++tail]=tr[u][1];
        insert(u,root[y],0);
        splay(u,root[y]);
    }
}