浅谈 Top Tree

· · Personal

浅谈 \rm Top\ Tree

标签：\rm Top\ Tree，维护子树动态树。

如果需要原始资料的话可以直接 QQ，基本上下文都是跑外网论文啃的。

零. 前言

本文将介绍三种能够支持 \rm LCT 原有操作，与子树修改的动态树 (树分块出门左拐)，重于介绍基础模板的实现，理解的难度由浅入深。三份代码细节都较多，代码实现难度可看个人。 （我觉得 \rm SATT 最好写)

  2. 动态树有时专指 \rm LCT，但本文中全部代表一类支持维护一颗动态形态的树的数据结构。
  3. 不建议拿这个数据结构来出题。
  4. 如果看到错误的话可以评论一下，如果您因为文章的错误挂了分的话可以来私信喷我，评论区面子受不住。
  5. 如果你是想学习这个数据结构，那么欢迎你往下看。如果你是被谋道毒瘤卡住，可以先看看这个，看完还是只有下数据结构能解决我们一起去喷出题人。

一. 引入

LCT 对链修改能十分容易的实现，维护虚儿子套路也屡见不鲜，子树信息查询也成为了经典问题。

问题引入：link

二. 初步探索

三. 动态开点线段树。

void ins_son(int &x,int y,data d,int L=1,int R=n) {
    if(!y)return;
    if(!x)x=new_node();
    if(L==R)return v[x].root=y,v[x].tsum=v[x].sum=d,void();
    int mid=(L+R)>>1;
    push_down(x);
    if(y<=mid)ins_son(v[x].ch[0],y,d,L,mid);
    if(mid<y)ins_son(v[x].ch[1],y,d,mid+1,R);
    push_up(x);
}
void del_son(int &x,int y,int p,int L=1,int R=n) {
    if(!y)return;
    if(L==R)return tag_tree(p,v[x].ttag,1),v[x]=node(1),x=0,void();
    int mid=(L+R)>>1;
    push_down(x);
    if(y<=mid)del_son(v[x].ch[0],y,p,L,mid);
    if(mid<y)del_son(v[x].ch[1],y,p,mid+1,R);
    push_up(x);
    if(!v[x].ch[0]&&!v[x].ch[1])S[++S[0]]=x,v[x]=node(1),x=0;
}
int access(int x) {
    int ret=0;
    for(int y=0; x; y=x,x=v[x].fa) {
        splay(x);
        if(y)del_son(v[x].root,v[y].pre,y);
    if(v[x].ch[1])ins_son(v[x].root,v[v[x].ch[1]].pre,v[v[x].ch[1]].sum);
        v[x].ch[1]=y,push_up(x),ret=x;
    }
    return ret;
}

四.平衡树

void add_son(int x,int t,int y) {
    v[x].ch[t]=y;
    v[y].fa=x;
}
int pos(int x) {
    for(int i=0; i<4; i++)if(v[v[x].fa].ch[i]==x)return i;
    return 4;
}
void ins_son(int x,int y) {
    if(!y)return;
    push_down(x);
    for(int i=2; i<4; i++) {
        if(!v[x].ch[i]) {
            add_son(x,i,y);
            return;
        }
    }
    while(v[x].ch[2]&&v[v[x].ch[2]].in)x=child(x,2);
    int z=new_node();
    add_son(z,2,v[x].ch[2]);
    add_son(z,3,y);
    add_son(x,2,z);
    splay(z,2);
}
void del_son(int x) {
    if(!x)return;
    splay(x);
    if(!v[x].fa)return;
    int p=v[x].fa;
    if(v[p].in) {
        int g=v[p].fa;
        pre_push_down(p,2);
        if(g) {
            add_son(g,pos(p),child(p,pos(x)^1));
            splay(g,2);
        }
        S[++S[0]]=p;
    } else {
        v[p].ch[pos(x)]=0;
        splay(p);
    }
    v[x].fa=0;
}
int get_fa(int x) {
    splay(x);
    if(!v[x].fa)return 0;
    if(!v[v[x].fa].in)return v[x].fa;
    int t=v[x].fa;
    splay(t,2);
    return v[t].fa;
}
int access(int x) {
    int ret=0;
    for(int y=0; x; y=x,x=get_fa(x)) {
        splay(x);
        del_son(y);
        ins_son(x,v[x].ch[1]);
        add_son(x,1,y);
        push_up(x);
        ret=x;
    }
    return ret;
}

五. \rm Self - Adjusting\ Top\ Trees

没有进行合并时，所有簇都是表示一个边，表示原树的一个边的簇称为 \rm base\ cluster。 我们可以把这两种操作看作合并两个簇，显然这两个簇合并之后还是簇。合并后，簇中可能和外部邻接的点是图上新边的端点，所以可以认为这个簇表示新边，表示的边的端点也就是簇的端点。显然，这样就可以一直合并到只剩一个簇。 我们可以对树进行若干轮收缩，每轮收缩执行 \rm rake 和 \rm compress 的一个极大独立操作集合，这样 \mathcal O(\log n) 轮收缩后，树就只剩一条边了。最后这条边对应的簇称为根簇 \rm (root cluster)。 收缩过程中，簇的合并结构形成了一个树，我们把这个树称为 \rm Top\ Tree。

那么我们就从简单的操作讲起，在只涉及 \rm splay 形态改变的操作 \rm rotate，

可以发现不管怎样，在父子关系上，代表子树的节点永远不会改变，可以直接像 LCT 那样实现，但是有可能父亲相对爷爷是代表子树节点特判一下即可。

if(g)v[g].ch[v[g].ch[2]==p?2:(v[g].ch[1]==p)]=x;

然后就是 \rm LCT 的核心操作 \rm access。在 tarjan 的论文中引入名为 \rm splice 的操作，表示将一个簇插入到他的父亲簇上。

可以发现，原来的 A 变成了 (A+chain_x+B)，原来的 (B+chain_y+C) 变成了 C。

这样就完成了簇与簇之间的插入。但是在 \rm access(x) 的时候，有可能 x 并不是当前簇上的末尾端点。

我们就先对 \rm x 进行一次 \rm local\ splay 然后把 \rm x 的右儿子暴力插入到 \rm x 的子树节点当中。剩下的簇与簇插入就交给 \rm splice 实现即可。

虽然在手动模拟算法时 $\rm AAAT$ 与 $\rm SATT$ 的操作相似，但是由于理论基础和操作细节的处理完全不一样，故常数应分开讨论。 ### 六.$\rm Contraction-based\ Top\ Tree

七. \rm Euler\ Tour\ Tree

后记

具体的实现细节可以去扒作者的代码，在轻重链剖分均有提交 (至于哪个对应哪一个就自己找一找) 。

作者的好朋友应该是他自己。

本来是想投 OI-wiki 的，但写完了又感觉完全配不上。于是就放在这里了。

最后求个赞（

upd：代码长度过于恐怖，四篇一起放这里顺序一一对应 code

upd：ETT 常数大是因为作者实现的时候没有省略非代表节点。

upd：还是看不懂可以加Q来问我。我可以从 LCT 只查询子树信息讲起。

upd： LCT - ETT 证明了是 O(n\log ^{2} n)

upd：AAAT 作者自己读了读，像shik一样，所以换上 @linfourxu 的代码（

upd：LCT - ETT 证明的是作者自己的实现，某WC Au+省队julao认为可以优化到 O(n\log n)。（假了）