极客资料网推荐LCT 学习笔记这篇文章给大家，欢迎收藏极客资料网享受知识的乐趣

动态树

注意作者有以下习惯：

#define el cout << '\n'
#define AC return 
#define AK return 0
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define void inline void
#define il inline

前置：splay

普通的二叉搜索树，为了使其保持深度为 \(\log n\)，每次将插入的点旋转到根。

代码在 lct 讲解部分会贴有。这里不讲解单独作为平衡树的写法，毕竟其不如 fhqtreap 一根。

rotate(x)

单次旋转，保证树的中序遍历不变。画个图可以理解。

splay(x)

将点旋转到根。

对于一个点，如果其父亲和自己都是其父亲的左或右儿子（即左右相同），转父亲均摊更优，否则转自己均摊更优。

单次最劣 \(O(n)\)，均摊 \(O( \log _2n)\)。

LCT

利用 splay 实现的文艺平衡树，维护动态树上区间问题，支持加边减边。

思想：实链剖分

树链剖分的一种。随意钦定点作为重儿子，方便维护动态的值。

实现

splay 部分

splay 充当文艺平衡树维护一个实链，左边为父亲，右边为儿子。

fa[x]

当 \(x\) 为所在 splay 的根，\(fa_x\) 为其在树上的父亲；
否则，\(fa_x\) 表示其在 splay 上的父亲。

push_up(i)

这个不用过多解释吧，根据题目要维护的信息写。

void push_up(int i) {
    siz[i] = siz[ls(i)] + siz[rs(i)] + 1;
    
}

push_down(i)

lct 上的 splay 需要支持区间反转。

void push_down(int i) {
    if(!tag[i]) AC;
    tag[ls(i)] ^= 1, tag[rs(i)] ^= 1;
    swap(ls(i), rs(i));
}

isrt(x)

返回 \(x\) 是否为所在 splay 的根。

#define isrt(x) (ls(fa[x]) ^ x && rs(fa[x]) ^ x)

lazytag(i)

暴力跳根并 pushdown 方便 splay 操作。

void lazytag(int i) {
    if(!isrt(i)) lazytag(fa[i]);
    push_down(i);
}

get(x)

若为 \(0\) 则为父亲的左儿子，\(1\) 为右儿子

#define get(x) (x == rs(fa[x]))

rotate(x)

void rotate(int x) {
    int y = fa[x], z = fa[fa[x]], tx = get(x), ty = get(fa[x]);
    if(!isrt(y)) ch[z][ty] = x;
    ch[y][tx] = ch[x][tx ^ 1], fa[ch[x][tx ^ 1]] = y;
    ch[x][tx ^ 1] = y, fa[y] = x, fa[x] = z; // 画图后很好理解
    push_up(y); push_up(x);
}

splay(x)

void splay(int x) {
    lazytag(x);
    while(!isrt(x)) {
        int y = fa[x], z = fa[fa[x]];
        if(!isrt(y)) {
            if((ls(z) == y) == (ls(y) == x)) rotate(y); // 全左和全右转父亲复杂度更优
            else rotate(x); // 非全左或全右转自己更优
        }
        rotate(x); // 转两次
    }
}

终于讲完 splay 了，果然是依托。

access(x)

将 \(x\) 到树根变成实链。整个 lct 最核心的功能，就像 split() 和 merge() 对于 fhqtreap 一样。有了 access() 就可以干很多事情了。

方法很暴力，将 \(x\) 到根上的所有点的所有 splay 暴力加进一个 splay 即可。

int access(int x) {
    for(int lst = 0; x; lst = x, x = fa[x]) {
        splay(x);
        rs(x) = lst;
        push_up(x);
        if(!fa[x]) break;
    }
    return x; // splay 的根
}

find(x)

找原树的父亲，注意会受后面 makeroot() 的影响。

int find(int x) {
    access(x);
    splay(x);
    while(ls(x)) x = ls(x);
    splay(x); // 转回去可以减小常数
    return x;
}

makeroot(x)

后面的函数就既好写又好理解了。

void makeroot(int x) {
    access(x);
    splay(x);
    tag[x] ^= 1;
    swap(ls(x), rs(x));
}

link(u, v)

添加 \(u\) 与 \(v\) 的边。

考虑将其中一个点所在树变为另一个的子树，这里我们选择 \(u\)。于是我们可以选择将 \(u\) 变成其子树的根并将 \(fa_u\) 改成 \(v\) 即可。

void link(int u, int v) {
    if(find(u) == find(v)) AC;
    makeroot(u);
    fa[u] = v;
}

cnt(u, v)

断掉 \(u\) 与 \(v\) 的边。

还是把其中一个转成根，另一个设成实链，splay 树上两点一定就是父亲与儿子的关系，直接修改即可。

void cut(int u, int v) {
    if(find(u) != find(v)) AC;
    makeroot(u); 
    access(v);
    splay(v);
    if(ls(v) == u) {
        ls(v) = 0;
        fa[u] = 0;
        push_up(v);
    }
}

完整代码

class LCT {
private:
    int ch[maxn][2], tag[maxn], siz[maxn], fa[maxn];
    void push_up(int i) {
        siz[i] = siz[ls(i)] + siz[rs(i)] + 1;
    }
    void push_down(int i) {
        if(!tag[i]) AC;
        tag[ls(i)] ^= 1, tag[rs(i)] ^= 1;
        swap(ls(ls(i)), rs(ls(i)));
        swap(ls(rs(i)), rs(rs(i)));
        tag[i] = 0;
    }
    #define isrt(x) (x ^ ls(fa[x]) && x ^ rs(fa[x]))
    void lazytag(int i) {
        if(!isrt(i)) lazytag(fa[i]);
        push_down(i);
    }
    #define get(x) (x == rs(fa[x]))
    void rotate(int x) {
        int y = fa[x], z = fa[fa[x]], tx = get(x), ty = get(fa[x]);
        if(!isrt(y)) ch[z][ty] = x;
        ch[y][tx] = ch[x][tx ^ 1], fa[ch[x][tx ^ 1]] = y;
        ch[x][tx ^ 1] = y, fa[y] = x, fa[x] = z; // 画图后很好理解
        push_up(y); push_up(x);
    }
    void splay(int x) {
        lazytag(x);
        while(!isrt(x)) {
            int y = fa[x], z = fa[fa[x]];
            if(!isrt(y)) {
                if((ls(z) == y) == (ls(y) == x)) rotate(y); // 全左和全右转父亲复杂度更优
                else rotate(x); // 非全左或全右转自己更优
            }
            rotate(x); // 转两次
        }
    }
    int access(int x) {
        for(int lst = 0; x; lst = x, x = fa[x]) {
            splay(x);
            rs(x) = lst;
            push_up(x);
            if(!fa[x]) break;
        }
        return x; // splay 的根
    }
    int find(int x) {
        access(x);
        splay(x);
        while(ls(x)) x = ls(x);
        splay(x); // 转回去可以减小常数
        return x;
    }
public:
    void makeroot(int x) {
        access(x);
        splay(x);
        tag[x] ^= 1;
        swap(ls(x), rs(x));
    }
    void link(int u, int v) {
        if(find(u) == find(v)) AC;
        makeroot(u);
        fa[u] = v;
    }
    void cut(int u, int v) {
        if(find(u) != find(v)) AC;
        makeroot(u); 
        access(v);
        splay(v);
        if(ls(v) == u) {
            ls(v) = 0;
            fa[u] = 0;
            push_up(v);
        }
    }
} ds;

文章来源:https://www.cnblogs.com/aceS0/p/19852367
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！