树链剖分 » 老官童鞋gogo的博客

树链剖分简介

链剖分

指对树的边进行划分的一种操作，目的是减少在链上修改、查询等操作的复杂度。链剖分分三类：轻重链剖分、虚实链剖分和长链剖分。

树链剖分思想

通过轻重链剖分将树分为多条链，保证每个节点都属于且只属于一条链。树链剖分时轻重链剖分，节点到重儿子，也就是到子树节点最多的儿子之间的路径就是重链。每条重链都相当于一段区间，把所有重链首尾相接组成的一个线性序列额，再通过数据结构（如树状数组、线段树、SBT、伸展树等）来维护即可。

基本结构

设$size[u]$表示以$u$为根的子树的节点个数，则在$u$的所有儿子中，$size$最大的儿子就是重儿子，而$u$的其他儿子都是轻儿子，当前节点与其重儿子之间的边就是重边，多条重边相连为一条重链。如下图中，标黑色的就是重链。

图片被我弄丢了……

图中长度大于$1$的重链有四条：$8 \rightarrow 4 \rightarrow 10 \rightarrow 16 \rightarrow 12$和$5 \rightarrow 9$和$6 \rightarrow 15$和$1 \rightarrow 13$。单个轻儿子可以看做是一条长度为$1$的重链，所以，图中共有$9$条重链。

重要性质

若$v$是轻儿子，$u$是$v$的父节点，则$size[v] \le \frac{size[u]}{2}$
从根到某一点路径上，不超过$\log n$条重链，不超过$\log n$条轻边

主要作用

单点修改：修改一个点的权值。
区间修改：修改节点$u$到节点$v$路径上的权值。
区间最值查询：查询节点$u$到$v$路径上的节点的最值。
区间和查询：查询节点$u$到$v$路径上节点的值。

树链剖分的应用比倍增更广泛，倍增可以做的，树链剖分一定可以，反过来则不行。

实现

树链剖分通过两次DFS实现。

第一次DFS

第一次DFS维护出四个值：

$dep[u]$
$fa[u]$
$size[u]$
$son[u]$

$dep[u]$表示节点$u$的深度；$fa[u]$表示节点u的父节点；$size[u]$表示以节点$u$为根节点的子树的节点数；$son[u]$表示重儿子$u$的重儿子为$son[u]$，即$u \rightarrow son[u]$是一条重边。

设我当前的节点为$u$，下一步是向更深的位置搜索，假设我搜索到的节点是$v$，那么dep[v]=dep[u]+1，fa[v]=u]。在递归回溯的时候，可以计算出size[u]+=size[v]，if(size[v]>size[son[u]]) son[u]=v。

void dfs1(int x,int f)
{
    size[x]=1;
    fa[x]=f;
    dep[x]=dep[f]+1;
    for(int k=g[x];k;k=e[k].nxt)
    {
        int y=e[k].to;
        if(y==f)
            continue;
        dfs1(y,x);
        size[x]+=size[y];
        if(size[y]>size[son[x]])
            son[x]=y;
    }
}

第二次DFS

第二次DFS，维护出另外三个值：

$top[u]$
$id[u]$
$rev[x]$

$top[u]$表示$u$所在的重链上的顶端节点编号，即重链上深度最小的节点。$id[u]$表示$u$在节点序列中的位置下标。$rev[x]$表示树链剖分后节点序列中第$x$个位置的节点。

其中，$id[u]$与$rev[x]$是互逆的。例如，节点$u$在节点序列中的位置下标是$x$，则节点序列中第x个位置的节点是$u$，$id[u]=x$，$rev[x]=u$。

在向下递归过程中，可以计算$top[u]$的值，这里的$u$表示当前节点，如果当前节点$u$是$fa[u]$的重儿子，top[u]=top[fa[u]]，否则top[u]=u。

void dfs2(int x)
{
    if(x==son[fa[x]])
        top[x]=top[fa[x]];
    else
        top[x]=x;
    for(int k=g[x];k;k=e[k].nxt)
    {
        int y=e[k].to;
        if(y==fa[x])
            continue;
        dfs2(y);
    }
}

求解$LCA$问题

对于$LCA$问题的求解，可以使用倍增和树剖两种方法，使用树剖解决这个问题更优。

首先通过两次DFS求出以上七个值中的五个（不包括$id[u]$和$rev[x]$），对于任意一对节点$(u,v)$只存在两种情况：

在同一条重链上（$top[u]=top[v]$）
不在一条重链上

对第一种情况，$LCA(u,v)$就是$u,v$中深度较小的节点。

对于第二中情况，我们就要想办法将两个节点转移到同一条重链上。首先求出$top[u]$和$top[v]$，将他们顶端节点深度较大的节点向上移，直到$u,v$在同一条重链上，再用第一种方法求解。

树链剖分与线段树

若在书中进行点更新、区间更新、区间查询等操作，则可以使用线段树来维护和处理。如下图：

来源：自己画的（没错，我又弄丢了）

图中点上的数字表示点的编号，周围的灰色数字为点权，加粗的边为重边，带阴影的点为重儿子。这些可以通过第一个循环做到。

树链剖分后的节点序列和下标序列如下：

	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
rev[]	1	3	6	10	8	7	2	5	9	4
	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
id[]	1	7	2	10	8	3	6	5	9	4

节点序列对应权值如下：

	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
w[]	20	3	8	5	30	16	6	1	15	12

根据$w[]$创建线段树，分别存下两个值：区间最值与和值。

查询节点$u$到节点$v$路径上的节点权值和最值的方法如下：

如果$u$和$v$在同一条重链上，则在线段树上查询其对应的下标区间[id[u],id[v]]即可。
如果$u$和$v$不在同一条重链上，我们需要一边查询，一边将$u$和$v$向同一条重链上移。当$top[u]!=top[v]$的时候，说明$u,v$两点不在同一条重链上，如果dep[top[u]]>dep[top[v]]，即点所在的重链链顶的深度大，就先把$top[u]$到$u$之间的最值与和值求出来，这样就转化成了第一种方法。然后把$u$节点修改为$fa[top[u]]$，进行同样的操作。

对于区间更新，方法与区间查询类似，如果不在一条链上，则一边更新，一边向同一条链上靠，在线段树上查询一条链上两个点之间区间的信息。

对于求解一棵子树的权值和，假设这颗子树的根节点为$u$，找到这棵子树中树链剖分后节点序列最大的一个点$v$，因为$w[i]$中存储的是连续的树链剖分后节点序列值，所以这棵子树的权值和是线段树上区间$[id[u],id[v]]$的和。修改同理。

代码（$LCA$问题）

来源：洛谷：P3379 【模板】最近公共祖先（LCA）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define reg register
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
#define M 1000001
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct Node
{
    int nxt,to;
}e[M];
int g[M],fa[M],dep[M],son[M],size[M],top[M],nxt,n,m,s;
void add(int x,int y)
{
    e[++nxt].to=y;
    e[nxt].nxt=g[x];
    g[x]=nxt;
}
void dfs1(int x,int f)
{
    size[x]=1;
    fa[x]=f;
    dep[x]=dep[f]+1;
    for(int k=g[x];k;k=e[k].nxt)
    {
        int y=e[k].to;
        if(y==f)
            continue;
        dfs1(y,x);
        size[x]+=size[y];
        if(size[y]>size[son[x]])
            son[x]=y;
    }
}
void dfs2(int x)
{
    if(x==son[fa[x]])
        top[x]=top[fa[x]];
    else
        top[x]=x;
    for(int k=g[x];k;k=e[k].nxt)
    {
        int y=e[k].to;
        if(y==fa[x])
            continue;
        dfs2(y);
    }
}
int LCA(int u,int v)
{
    while(top[u]!=top[v])
        dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
    return dep[u]>dep[v]?v:u;
}
int main()
{
    n=read(),m=read(),s=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        add(u,v);
        add(v,u);
    }
    dfs1(s,0);  
    dfs2(s);
    while(m--)
    {
        int a=read(),b=read();
        printf("%d\n",LCA(a,b));
    }
    return 0;
}

代码（线段树维护树链剖分）

来源：洛谷：P3384 【模板】轻重链剖分/树链剖分

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define LL long long
#define uLL unsigned long long
#define reg register
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
#define M 200001
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
struct Node1
{
    int nxt,to;
}e[M];
struct Node2
{
    int l,sum;
}tree[4*M];
int g[M],size[M],dep[M],f[M],w[M],son[M],rev[M],id[M],top[M];
int n,m,rt,mod,cnt,nxt;
void add(int x,int y)
{
    e[++nxt].to=y;
    e[nxt].nxt=g[x];
    g[x]=nxt;
}
void dfs1(int x,int fa)
{
    size[x]=1;
    for(int k=g[x];k;k=e[k].nxt)
    {
        int y=e[k].to;
        if(y==fa)
            continue;
        dep[y]=dep[x]+1;
        f[y]=x;
        dfs1(y,x);
        size[x]+=size[y];
        if(size[y]>size[son[x]])
            son[x]=y;
    }
    return;
}
void dfs2(int x,int t)
{
    top[x]=t;
    id[x]=++cnt;
    rev[cnt]=x;
    if(!son[x])
        return;
    dfs2(son[x],t);
    for(int k=g[x];k;k=e[k].nxt)
    {
        int y=e[k].to;
        if(y!=f[x]&&y!=son[x])
            dfs2(y,y);
    }
    return;
}
void pushdown(int i,int l,int r)
{
    if(tree[i].l!=0)
    {
        int mid=(l+r)>>1;
        tree[i<<1].l+=tree[i].l;
        tree[i<<1|1].l+=tree[i].l;
        tree[i<<1].l%=mod;
        tree[i<<1|1].l%=mod;
        tree[i<<1].sum+=tree[i].l*(mid-l+1);
        tree[i<<1|1].sum+=tree[i].l*(r-mid);
        tree[i<<1].sum%=mod;
        tree[i<<1|1].sum%=mod;
        tree[i].l=0;
    }
    return;
}
void build(int i,int l,int r)
{
    if(l==r)
    {
        tree[i].sum=w[rev[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    tree[i].sum%=mod;
    return;
}
int search(int i,int nl,int nr,int l,int r)
{
    if(nl>=l&&nr<=r)
    {
        return tree[i].sum;
    }
    int mid=(nl+nr)>>1,s=0;
    pushdown(i,nl,nr);
    if(l<=mid)
        s+=search(i<<1,nl,mid,l,r);
    if(r>mid)
        s+=search(i<<1|1,mid+1,nr,l,r);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    tree[i].sum%=mod;
    return s%mod;
}
void change(int i,int nl,int nr,int l,int r,int k)
{
    if(nl>=l&&nr<=r)
    {
        tree[i].l+=k;
        tree[i].sum+=k*(nr-nl+1);
        return;
    }
    pushdown(i,nl,nr);
    int mid=(nl+nr)>>1;
    if(l<=mid)
        change(i<<1,nl,mid,l,r,k);
    if(r>mid)
        change(i<<1|1,mid+1,nr,l,r,k);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    tree[i].sum%=mod;
    return;
}
void tree_change(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        change(1,1,n,id[top[x]],id[x],z);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    change(1,1,n,id[x],id[y],z);
}
int tree_search(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        ans+=search(1,1,n,id[top[x]],id[x]);
        ans%=mod;
        x=f[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    ans+=search(1,1,n,id[x],id[y]);
    return ans%mod;
}
void son_tree_change(int x,int z)
{
    change(1,1,n,id[x],id[x]+size[x]-1,z);
}
int son_tree_search(int x)
{
    return search(1,1,n,id[x],id[x]+size[x]-1);
}
int main()
{
    read(n),read(m),read(rt),read(mod);
    for(int i=1;i<=n;i++)
        read(w[i]);
    for(int i=1;i<n;i++)
    {
        int x,y;
        read(x),read(y);
        add(x,y);
        add(y,x);
    }
    dfs1(rt,0);
    dfs2(rt,rt);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int opt;
        read(opt);
        if(opt==1)
        {
            int x,y,z;
            read(x),read(y),read(z);
            tree_change(x,y,z);
        }
        if(opt==2)
        {
            int x,y;
            read(x),read(y);
            print(tree_search(x,y));
            putchar('\n');
        }
        if(opt==3)
        {
            int x,z;
            read(x),read(z);
            son_tree_change(x,z);
        }
        if(opt==4)
        {
            int x;
            read(x);
            print(son_tree_search(x));
            putchar('\n');
        }
    }
    return 0;
}