LCT

Lofty · 2024-11-21 21:33:54 · 算法·理论

前言

树链剖分中的实链剖分。前面已经讲过重链剖分和长链剖分了，实链剖分也早学了，来补上blog。

Link-Cut Tree

LCT，全名 Link-Cut Tree，是一个非常强大的维护两点之间的路径信息的数据结构，相比于重链剖分只能维护静态的一棵树，实链剖分可以维护动态的森林，且复杂度并没有什么改变。但是这玩意比重链剖分难学难写难理解，所以能简化不用是最好的。 LCT 基于 Splay 树，但在具体操作有些不同。在 LCT 中，每一条链都是一棵 Splay 树且没有明确的父子关系，依靠 Splay 强大性质，复杂度仍然可以保持良好。

这里以 luogu 模板题 P3690 为例。

关联元素：

对于该节点的更新。

void pushup(int x)
{
    tr[x].sum=tr[ls(x)].sum^tr[x].v^tr[rs(x)].sum;
}

2. pushdown

懒标记的下转和更新。

void pushdown(int x)//下传懒标记
{
    if(tr[x].tag)
    {
        swap(ls(x),rs(x));//翻转
        tr[ls(x)].tag^=1;
        tr[rs(x)].tag^=1;
        tr[x].tag=0;
    }
}

注意：这种写法会认为上传信息时左右儿子的顺序是无关的，若有关时，在 pushup 前 pushdown 即可。

3. pushall

对当前链懒标记全部下传，用于 splay 前调整树的结构。

void pushall(int x)//全部下传
{
    if(notroot(x))pushall(fa(x));
    pushdown(x);
}

4. rotate

splay 中的旋转操作，但小做改动。

void rotate(int x)//旋转
{
    int y=fa(x),z=fa(y);
    int k=get(x);
    if(notroot(y))//不改变虚边
        tr[z].c[get(y)]=x;
    fa(x)=z;
    tr[y].c[k]=tr[x].c[k^1];
    fa(tr[x].c[k^1])=y;
    tr[x].c[k^1]=y;
    fa(y)=x;
    pushup(y),pushup(x);//先 y 后 x（y 已经是 x 的儿子了）
}

5. splay

旋转至 splay 的根节点。

void splay(int x)//保证复杂度，并旋转至根节点
{
    pushall(x);//先调整树的结构
    while(notroot(x))
    {
        int y=fa(x);
        if(notroot(y))
            (get(x)^get(y))?rotate(x):rotate(y);
        rotate(x);
    }
}

6. access

将 x 与当前整棵树的根节点之间的路径单独成一棵 splay 树。 LCT 的关键操作。

void access(int x)//重组实链，打通从x到全树根节点的链，全部改成实边，链上原有的其他边改为虚边
{
    for(int y=0;x;y=x,x=fa(x))
    {
        splay(x);//先旋转至根
        rs(x)=y;//原右儿子改为虚边，y改为实边
        pushup(x);
    }
}

7. makeroot

使 x 节点成为整棵树的根。

void makeroot(int x)
{
    access(x);
    splay(x);
    tr[x].tag^=1;//这里对于根到 x 的路径，深度是反转的，加上中序遍历深度递增的性质，做一次翻转子树即可维护
}

8. findroot

找到整棵树的根节点。

int findroot(int x)
{
    access(x);
    splay(x);
    while(ls(x))
        pushdown(x),x=ls(x);
    splay(x);//这里视情况决定写不写，主要用于防止一条长链来回搜，毒瘤出题人会在这里卡常
    return x;
}

9. split

分离出 x 到 y 的一条链。

void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}

10. check

这个函数为个人爱好，判断 x 和 y 在不在同一个联通块里。

bool check(int x,int y)
{
    makeroot(x);
    return findroot(y)==x;
}

11. link

连接 x 和 y。

bool link(int x,int y)
{
    if(check(x,y))
        return false;
    fa(x)=y;
    return true;
}

12. cut

切断 x 和 y

bool cut(int x,int y)
{
    if(!check(x,y)||ls(y)||fa(y)!=x)
        return false;
    rs(x)=fa(y)=0;
    return true;
}

13. modify

单点修改。

void modify(int x,int c)
{
    splay(x);
    tr[x].val=c;
    //or do something...
    pushup(x);
}

14. query

询问 x 到 y 的链的信息。

int query(int x,int y)
{
    split(x,y);
    return tr[y].sum;
}

复杂度

空间复杂度 O(n)，时间复杂度 splay 一次的复杂度均摊至 O(\log n)，总复杂度为调用 splay 次数 T \times O(\log n)，即 O(T\log n)。但大多数操作里只调用一两次，约为询问次数 q \times O(\log n)，即 O(q\log n)。

Code：

模板 LCT

完整代码：

namespace Lofty
{
    namespace LCT
    {
        struct trnode
        {
            int ch[2],fa,val,sum;//ch：儿子，fa：父亲，val：当前点的权值，：sum：以当前点为根的树的权值
            int tag;//懒标记
        }tr[N];
        #define ls(x) tr[x].ch[0]
        #define rs(x) tr[x].ch[1]
        #define fa(x) tr[x].fa
        #define notroot(x) (ls(fa(x))==x||rs(fa(x))==x)
        #define get(x) (rs(fa(x))==x)
        void pushup(int x)
        {
            tr[x].sum=tr[ls(x)].sum^tr[x].val^tr[rs(x)].sum;//左儿子异或当前点权值异或右儿子
        }
        void pushdown(int x)//下传懒标记
        {
            if(tr[x].tag)
            {
                swap(ls(x),rs(x));//翻转
                tr[ls(x)].tag^=1;
                tr[rs(x)].tag^=1;
                tr[x].tag=0;
            }
        }
        void pushall(int x)//全部下传
        {
            if(notroot(x))
                pushall(fa(x));//懒标记一般在根节点处，要向上找并下传
            pushdown(x);
        }
        void rotate(int x)//旋转
        {
            int y=fa(x),z=fa(y);
            int k=get(x);
            if(notroot(y))//不改变虚边
                tr[z].ch[get(y)]=x;
            fa(x)=z;
            tr[y].ch[k]=tr[x].ch[k^1];//连边
            fa(tr[x].ch[k^1])=y;
            tr[x].ch[k^1]=y;//连边
            fa(y)=x;
            pushup(y),pushup(x);//先y后x（y已经是x的儿子了）
        }
        void splay(int x)//保证复杂度，并旋转至根节点
        {
            pushall(x);
            while(notroot(x))//还没转到根节点
            {
                int y=fa(x);
                if(notroot(y))//尝试能否转两次
                    (get(x)^get(y))?rotate(x):rotate(y);//如果y和x对于父亲而言都是同一方向的儿子，要先转y,才能保证y的另一个儿子是正确的，否则y可能成为一条链？
                rotate(x);
            }
        }
        void access(int x)//重组实链，打通从x到全树根节点的链，全部改成实边，链上原有的其他边改为虚边
        {
            for(int y=0;x;y=x,x=fa(x))
            {
                splay(x);//先旋转至根
                rs(x)=y;//原右儿子改为虚边，y改为实边
                pushup(x);
            }
        }
        void makeroot(int x)//将x换到全树的根节点，把树倒过来
        {
            access(x);//先打通，才能在同一棵splay树里
            splay(x);//已经在一棵splay树里了，直接旋转到根节点
            tr[x].tag^=1;//翻转，保证中序遍历深度是递增的
        }
        void split(int x,int y)//将x和y的路径与其他路径分离
        {
            makeroot(x);//先成为根节点，后面才能打通y到x的路径
            access(y);//打通y到根节点（x）的路径
            splay(y);
        }
        int findroot(int x)//找到根节点
        {
            access(x);//先打通
            splay(x);//旋转到根节点
            while(ls(x))//这时因为中序遍历的深度是递增的，我们只要找左儿子就可以找到深度最小的节点，那就是根节点
                pushdown(x),x=ls(x);
            splay(x);//防止卡一条链来回搜
            return x;
        }
        bool check(int x,int y)
        {
            makeroot(x);
            return findroot(y)==x;
        }
        bool link(int x,int y)//连边
        {
            if(check(x,y))
                return false;//如果已经是同一棵splay树了，那先前已经让x成为splay树的根了，找到的根就应是x，那就不应该连
            fa(x)=y;//y不是x所在的splay树，而splay树的根节点只能向另一个splay树的节点连一条虚边
            return true;
        }
        bool cut(int x,int y)//断边
        {
            if(!check(x,y)||fa(y)!=x||ls(y))
                return false;//不在同一棵splay树上或者没有直接相连,又或者y不是x的后继，中序遍历中还有其他节点
            rs(x)=fa(y)=0;//断开边
            pushup(x);//少了个儿子，要更新上传，权值会改变
            return true;
        }
        void modify(int x,int c)//更改权值
        {
            splay(x);//先转到根节点，不要影响了其他节点
            tr[x].val=c;
            pushup(x);//节点权值改了，也要更新上传，权值会改变
        }
        int query(int x,int y)//输出
        {
            split(x,y);
            return tr[y].sum;//信息保存在splay树的根节点
        }
        //以上就是模板LCT，实质上是将树拆成许多条实链，用splay维护，这两玩意儿都比较难理解
        //时间复杂度O(mlogn) 
    }
    void work()
    {
        int T=1;
        // read(T);
        while(T--)
        {
            int n,m;read(n,m);
            for(int i=1;i<=n;i++)
                read(LCT::tr[i].val);
            while(m--)
            {
                int op;read(op);
                switch(op)
                {
                    int x,y;
                    case 0:
                        read(x,y);
                        writeln(LCT::query(x,y));
                        break;
                    case 1:
                        read(x,y);LCT::link(x,y);
                        break;
                    case 2:
                        read(x,y);LCT::cut(x,y);
                        break;
                    case 3:
                        read(x,y);LCT::modify(x,y);
                        break;
                }
            }
        }
    }
}