主题

主题

 
   

关于Splay代码调整笔记

  • 杂谈

看到别人的代码,感觉自己的研究还不够深。


  • tag定义

我写的Splay中,如果节点p有tag,则表示节点p以及其子树全部没有被修改。

然后看到别人的tag都是和Seg一致的定义,表示节点p的儿子没有被修改。

首先是标记,下放标记和上传标记最好分开写,否则的话非常容易出问题。

我们下放标记记录的是孩子结点的信息,所以我们如果要对一个结点打标记,我们要先处理好这个结点,比如说这个结点权值加上一个值,左右子树交换等等。

(来源:http://blog.csdn.net/lyhypacm/article/details/6630582


  • tag统一化

不管是区间翻转这样的标记,还是说区间加区间乘这样的标记,均采用“记录儿子信息”的方式。

不同标记的统一,以及Splay与Seg标记的统一。


  • tag下传

有的大佬是在旋到根之前就把tag全部下传(由此只有上文提及的“记录儿子信息的tag”才可以实现),本蒟感觉不太优美。毕竟在复杂度证明的时候,仅仅是证明了从x直接旋转到根的复杂度,没有证明从根找到x的复杂度。

但是似乎是差不多的。旋转事实上也经历了那么多的时间。

虽然说双旋本来就在调整树的形态使之平衡。但是我还是不打算这样写。

那么引用一段我觉得下传tag不错的代码:

void splay(int x,int goal)  

{  

    int y,z,kind;  

    while (pre[x]!=goal)  

    {  

        y=pre[x];down(y);  

        if (pre[y]==goal) rot(x,c[y][0]==x);  

        else  

        {  

            z=pre[y];down(z);kind=c[z][0]==y;  

            if (c[y][!kind]==x) rot(y,kind);else rot(x,!kind);  

            rot(x,kind);  

        }  

    }  

    if (goal==0) root=x;  

}  

(来源:http://blog.csdn.net/tag_king/article/details/45111473

这是在Splay函数里面pushdown的。另外看到一位大佬的也不错(比较符合我之前的风格),在rot函数里面pushdown。

inline void rotate(int now)    

    {

        PushDown(fa[now]); PushDown(now);

        int f=fa[now],gf=fa[f],wh=Right(now);

        son[f][wh]=son[now][wh^1]; fa[son[f][wh]]=f;

        fa[f]=now; son[now][wh^1]=f; fa[now]=gf;

        if (gf) son[gf][son[gf][1]==f]=now;

        Update(f); Update(now);

    }

    inline void splay(int now,int tar)

    {

        for (int f; (f=fa[now])!=tar; rotate(now))

            if (fa[f]!=tar) rotate(Right(now)==Right(f)? f:now);

        if (!tar) root=now;    

    }

(来源:http://www.cnblogs.com/DaD3zZ-Beyonder/p/5861000.html

还有一个思想,似乎是针对了x多次被pushdown与update来优化的。在rot里面只有一个pushup(即update),在末尾update一次:

    void rotate(int x,int f){  

        int y = pre[x];  

        push_down(x);  

        push_down(y);  

        ch[y][!f] = ch[x][f];  

        if(ch[y][!f]) pre[ch[y][!f]] = y;  

        push_up(y); 

        if(pre[y]) ch[pre[y]][r(pre[y])==y] = x;  

        pre[x] = pre[y];  

        ch[x][f] = y;  

        pre[y] = x;  

    }  

    void splay(int x,int goal){  

        while(pre[x]!=goal){  

            int y = pre[x],z = pre[pre[x]];  

            if(z==goal){  

                rotate(x,l(y)==x);  

            }else{  

                int f = l(z)==y;  

                if(ch[y][!f]==x){  

                    rotate(y,f); rotate(x,f);  

                }else{  

                    rotate(x,!f); rotate(x,f);  

                }  

            }  

        }  

        push_up(x);  

        if(goal==0) root = x;  

    }  

(来源:http://coco-young.iteye.com/blog/1786433

看了Hzwer的Splay代码不是很懂,那个“Find”操作是干啥的……


  • 本蒟的处理

然后自己写了一份,关于区间加与区间查询的。

这是三部分函数,与Seg是一致的:

void unite(int p) {

    Btr[p].sum=Btr[Btr[p].s[0]].sum+Btr[Btr[p].s[1]].sum+Btr[p].val;

    size[p]=size[Btr[p].s[0]]+size[Btr[p].s[1]]+1;

}

void update(int p,int w) {

    Btr[p].sum+=(long long)size[p]*w;

    Btr[p].val+=w;

    Btr[p].tag+=w;

}

void down(int p) {

    if(!Btr[p].tag)return;

    update(Btr[p].s[0],Btr[p].tag);

    update(Btr[p].s[1],Btr[p].tag);

    Btr[p].tag=0;

}

接下来是旋转的部分,在赋值完f与gf之后下传标记。

int f,gf,s,v;

void rot(int p) {

    f=Fa[p]; gf=Fa[f]; down(f); down(p); v=Btr[f].s[0]!=p;

    s=Btr[p].s[v^1]; Btr[p].s[v^1]=f; Btr[f].s[v]=s; Fa[s]=f; Fa[p]=gf; Fa[f]=p; unite(f); unite(p);

    if(gf) {v=Btr[gf].s[0]!=f; Btr[gf].s[v]=p;}

}

这样想比原来常数减小了许多。


  • 关于双旋

之前是一个彻头彻尾的单旋党。

后来看完复杂度证明之后明白了单旋确实危险。转为了双旋。

双旋的代码也就增加了几行。

void Splay(int p) {

    for(f=Fa[p],gf=Fa[f]; Fa[p]&&Fa[f]; rot(p),f=Fa[p],gf=Fa[f])

    rot((Btr[gf].s[0]!=f)^(Btr[f].s[0]!=p)?p:f);

    if(Fa[p])rot(p); root=p;

}

即可。

在双旋之中也不必下传标记什么的。这样也减少了在外面调用rot函数的风险。


  • 关于修改与查询

修改的话,我们只需要把更新关键节点,合并前驱后继节点:

void Change(int l,int r,int w) {

    Splay(r+2); Splay(l); if(Btr[l].s[1]!=r+2)rot(r+2);

    update(Btr[r+2].s[0],w); unite(r+2); unite(l);

}

至于查询,同样只需要下传前驱后继的标记:

long long Getsum(int l,int r) {

    Splay(r+2); Splay(l); if(Btr[l].s[1]!=r+2)rot(r+2);

    down(l); down(r+2); return Btr[Btr[r+2].s[0]].sum;

}

果然不出所料,随机数据下单旋比双旋快。

完整代码(以codevs_1082为例):https://code.csdn.net/snippets/2220772


  • 不同tag的韵味

今天写LCT的时候被匡了。

然后就去问LCF大爷他的Splay是怎么写的。

LCF大爷说,对于不同的标记可以不同处理,有一些可以标记当前节点的信息,有一些可以标记儿子的。

然后自己想了一下,看了别人写的LCT的代码。

搬了一个:

void splay(int x) {

    q[++top]=x;

    for(int i=x; !isroot(i); i=fa[i]) {

        q[++top]=fa[i];

    }

    while(top)push_down(q[top--]);

    for(int y=fa[x]; !isroot(x); rotate(x),y=fa[x]) {

        if(!isroot(y)) {

            if((lc(y)==x)^(lc(fa[y])==y))rotate(x);

            else rotate(y);

        }

    }

    push_up(x);

}

void access(int x) {

    for(int t=0; x; t=x,x=fa[x]) {

        splay(x);

        ch[x][1]=t;

        push_up(x);

    }

}

(来源:http://www.cnblogs.com/ezyzy/p/6390475.html

然后发现大佬的inv标记是记录当前节点的信息的,即x有一个inv标记表示x的儿子需要交换。然后我又有一大堆记录当前节点儿子信息的tag。然后就瞎YY了一个方法。

如果需要下传的是标记自己节点的标记,我们就在Splay过程里面把标记下传。比方说inv标记。就像这样:

    void Splay(int p) {

        for(v=p; !Beroot(v); v=fa[v])stk[++stktop]=v; stk[++stktop]=v;

        for(; stktop; stktop--)flip(stk[stktop]);

        for(f=fa[p],gf=fa[f]; !Beroot(f)&&!Beroot(p); rot(p),f=fa[p],gf=fa[f])

                if((Btr[gf].s[0]!=f)^(Btr[f].s[0]!=p))rot(f);else rot(p);

        if(!Beroot(p))rot(p);

    }

如果需要下传的是标记儿子的节点,就在rot里面下传。比方说plus的标记。在之前就已经贴过了,这里不再赘述。

当然都可以在Splay函数里面下传。这样大概常数会小一些。


  • 总结出来的约定

在普通的Splay中,直接在rot里面下传。

在LCT以及需要混合tag的时候,在Splay函数里面下传

 
 
评论