浅谈树链剖分（上）

P_Bisector · 2023-11-20 22:34:23 · 个人记录

本文极其适合包括刚刚学完树的定义的OIer在内的OIer。~~是人都能看懂。~~

例题：

P3379 LCA

虽然说树链剖分和LCA没啥关系，正式比赛时大家也多用倍增算法为主，但是在这里算是一个引子吧。

LCA，最近公共祖先，即两个点之间深度最大~~最亲民~~的公共祖先。比如这么一棵树：

father[2]=4
father[1]=4
father[3]=1
father[5]=1

（father表示一个节点的父亲节点编号。）我们假设de_x是x节点的深度，LCA(x,y)是x,y两个节点的最近公共祖先。如果de_x>de_y，那么LCA(x,y)=LCA(Father_x,y)，反之亦然。如果de_x=de_y的话，LCA(x,y)=LCA(Father_x,Father_y)。接下来我们就可以有一份TLEcode了：

int LCA(int a,int b){
    while(a!=b){
        if(de[a]<de[b]){//将a设为深度较小的那个
            swap(a,b);
        }
        a=fa[a];//a往上跳
    }
    return a;
}

这个思路很显然不是最优的。~~事实上，它非常烂。~~ 它的时间复杂度最坏是O(nm)。我们来分析一下它的缺点。每一操作后，它都只能跳一条边。如果我们可以把树拆成多条链，每次跳到链顶节点的父亲节点，就可以避免大量的重复操作。 但是我在这里提醒一下大家，此时每次跳跃过程中我们操作的是其中链顶节点的深度较大的那一个，而不是当前节点。

code:

void dfs(int x,int tp){//x表示当前dfs到的节点，tp表示该节点所在链的顶端节点编号
    de[x]=de[fa[x]]+1;
    top[x]=tp;
    int flag=0;
    for(int i=0;i<g[x].size();i++){
        if(g[x][i]!=fa[x]){
            int v=g[x][i];
            fa[v]=x;
            if(flag==1){//不是第一个点
                dfs(v,v);//从这个点开始新建一条链
            }else{//是第一个点
                flag=1;
                dfs(v,tp);//和原来的节点并入同一条链
            }
        }
    }
}
int LCA(int a,int b){
    while(top[a]!=top[b]){//只要不在同一条链上
        if(de[top[a]]<de[top[b]]){//注意！比较所在链顶部节点的深度
            swap(a,b);
        }
        a=fa[top[a]];//先跳一条链，再跳一条边
    }
    if(de[a]<de[b])swap(a,b);//返回其深度较小的
    return b;
}

这个代码时间复杂度仍然是O(nm)。举个例子吧，比如以下毒瘤数据：

root=1
father[2]=1
father[3]=1
father[4]=3
father[5]=3
father[6]=5
father[7]=5
…………
father[2*i]=2*i-1
father[2*i+1]=2*i-1

对于以上情况，我们会惊奇的发现，每一条链长度只有2！如果我们从节点500000开始跳跃，需要跳跃大约500000次！如何才能使跳跃次数足够小呢？

假设跳跃前节点为x，跳跃后节点为y，如果以y为根的子树的大小（以下简称sze_y）是sze_x的两倍甚至更多，那么即使从x跳到根（root）也不过跳跃log_{2}n次。为了满足这一条件，我们可以对上面的剖分方式进行修改：如果2sze_x<sez_{father_x}，那么就不计入一条链；否则计入一条。 另外，我们还可以对该规则简化：如果x是father_x当中sze_x最大的子节点，那么该节点被称为father_x的重儿子并与father_x计入一条链。

AC code:

#include<iostream>
#include<vector>
using namespace std;
vector<int>g[500005];
int de[500005],fa[500005],top[500005],sze[500005],son[500005];
void dfs(int x){
    de[x]=de[fa[x]]+1;
    sze[x]=1;//注意！节点本身也算入
    for(int i=0;i<g[x].size();i++){
        if(g[x][i]!=fa[x]){
            int v=g[x][i];
            fa[v]=x;
            dfs(v);
            sze[x]+=sze[v];//记录子树大小
            if(sze[v]>sze[son[x]]){
                son[x]=v;//处理重儿子
            }
        }
    }
}
void dfs2(int x,int tp){
    if(x==0)return;//防止重儿子为0
    top[x]=tp;
    dfs2(son[x],tp);//计入同一链
    for(int i=0;i<g[x].size();i++){
        if(g[x][i]!=fa[x]&&g[x][i]!=son[x]){
            int v=g[x][i];
            dfs2(v,v);
        }
    }
}
int LCA(int a,int b){
    while(top[a]!=top[b]){
        if(de[top[a]]<de[top[b]]){
            swap(a,b);
        }
        a=fa[top[a]];
    }
    if(de[a]<de[b])swap(a,b);
    return b;
}
int main(){
    int n,q,r;
    cin>>n>>q>>r;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(r);
    dfs2(r,r);//dfs两遍
    for(int i=0;i<q;i++){
        int x,y;
        cin>>x>>y;
        cout<<LCA(x,y)<<endl;
    }
    return 0;
}

时间复杂度分析：

DFS$：$O(n)

LCA$：$O(logn)

总时间复杂度：O(n+mlogn)（比倍增还优秀一点）

空间复杂度：O(n)（比倍增还优秀好多）

总结：本篇博客以LCA为引子简单介绍了树链剖分。若有不懂或不明白之处，欢迎提出。