树链剖分

· · 个人记录

简介

树链剖分，顾名思义，就是将一棵树解剖成若干条链，再进行修改和查询。这样能将 \mathcal{O(n)} 的操作压缩到 \mathcal{O(\log n)} 级别。

分类

  1. 重链剖分

模板

主要就是进行对于路径和子树的修改查询操作。

  1. 1 定义

重儿子：儿子中子树最大的儿子。

重边：连接父亲与重儿子的边。

重链：一条由多条重边连成的链。

  1. 2 性质

数量不超过 \log n 条。

每个节点都分别存在于一条重链中。

重链的顶端是链中最浅的节点。

  1. 3 应用

先分析怎么用。

首先，对于 u 到 v 的一条路径，我们假设 u 所在重链的顶端深度更深，那么就修改（查询）u 到顶端的这条路径，再将 u 变为顶端的父亲，继续操作，直到 u,v 存在于同一条重链上，直接操作。

其次，对于 u 的子树，可以直接查询。

以上两个操作都需要线段树加成。详见 \mathrm{dfs2}。

预处理出每个节点的父亲，深度，子树大小，及其重儿子。

il void dfs1(re int u,re int fa) {
    dep[u]=dep[fa]+1;
    f[u]=fa;
    siz[u]=1;
    for(re int i=head[u],v,_max=0;i;i=nxt[i]) {
        v=to[i];
        if(v==fa) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>_max) {
            son[u]=v;
            _max=siz[v];
        }
    }
}

这里需要编号。对于每个节点，优先走重儿子，到达每个节点将编号加一。这样就方便查询了。

对于路径，重链上的节点编号是连续的，线段树上方便操作。

对于子树，编号也是连续的，同理。

这一层 \mathrm{dfs} 需要记录编号，及其重链顶端节点编号。


il void dfs2(re int u,re int _top) {
    id[u]=++tot;
    b[id[u]]=a[u];
    top[u]=_top;
    if(!son[u]) return ;
    dfs2(son[u],_top);
    for(re int i=head[u],v;i;i=nxt[i]) {
        v=to[i];
        if(v==f[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

接下来就是线段树的基本操作了。

#include<bits/stdc++.h>
#define il inline
#define re register
#define int long long
using namespace std;

const int N=1e5+10,M=2e5+10;

int n,m,root,mod;

int to[M],nxt[M],cnt,head[N];

int dep[N],f[N],siz[N],son[N],a[N];

int id[N],b[N],top[N],tot,x[N<<2],tag[N<<2];

il void Mod(re int &x) { x=(x>=mod?x-mod:x); }

il void qian(re int u,re int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

il void dfs1(re int u,re int fa) {
    dep[u]=dep[fa]+1;
    f[u]=fa;
    siz[u]=1;
    for(re int i=head[u],v,_max=0;i;i=nxt[i]) {
        v=to[i];
        if(v==fa) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>_max) {
            son[u]=v;
            _max=siz[v];
        }
    }
}

il void dfs2(re int u,re int _top) {
    id[u]=++tot;
    b[id[u]]=a[u];
    top[u]=_top;
    if(!son[u]) return ;
    dfs2(son[u],_top);
    for(re int i=head[u],v;i;i=nxt[i]) {
        v=to[i];
        if(v==f[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

il void pushup(re int p) {
    Mod(x[p]=x[p<<1]+x[p<<1|1]);
}

il void build(re int p,re int l,re int r) {
    if(l==r) {
        x[p]=b[l];
        return ;
    }
    re int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}

il void pushdown(re int p,re int l,re int r) {
    if(!tag[p]) return ;
    re int mid=(l+r)>>1;
    Mod(tag[p<<1]+=tag[p]);
    Mod(tag[p<<1|1]+=tag[p]);
    Mod(x[p<<1]+=tag[p]*(mid-l+1)%mod);
    Mod(x[p<<1|1]+=tag[p]*(r-mid)%mod);
    tag[p]=0;
}

il void modify(re int p,re int l,re int r,re int L,re int R,re int k) {
    if(L<=l&&r<=R) {
        Mod(x[p]+=k*(r-l+1)%mod);
        Mod(tag[p]+=k);
        return ;
    }
    pushdown(p,l,r);
    re int mid=(l+r)>>1;
    if(L<=mid) modify(p<<1,l,mid,L,R,k);
    if(R>mid) modify(p<<1|1,mid+1,r,L,R,k);
    pushup(p);
}

il int query(re int p,re int l,re int r,re int L,re int R) {
    if(L<=l&&r<=R) {
        return x[p];
    }
    pushdown(p,l,r);
    re int mid=(l+r)>>1,ret=0;
    if(L<=mid) {
        Mod(ret+=query(p<<1,l,mid,L,R));
    }
    if(R>mid) {
        Mod(ret+=query(p<<1|1,mid+1,r,L,R));
    }
    pushup(p);
    return ret;
}

il void update1(re int u,re int v,re int k) {
    k%=mod;
    while(top[u]!=top[v]) {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        modify(1,1,n,id[top[u]],id[u],k);
        u=f[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    modify(1,1,n,id[u],id[v],k);    
}

il void update2(re int u,re int k) {
    k%=mod;
//  cout<<id[u]<<' '<<id[u]+siz[u]-1<<'\n';
    modify(1,1,n,id[u],id[u]+siz[u]-1,k);
}

il int query1(re int u,re int v) {
    re int ret=0;
    while(top[u]!=top[v]) {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        Mod(ret+=query(1,1,n,id[top[u]],id[u]));
        u=f[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    Mod(ret+=query(1,1,n,id[u],id[v]));     
    return ret;
}

il int query2(re int u) {
    return query(1,1,n,id[u],id[u]+siz[u]-1);
}

signed main() {
//  freopen("P3384_1.in","r",stdin);
    scanf("%lld%lld%lld%lld",&n,&m,&root,&mod);
    for(re int i=1;i<=n;i++) {
        scanf("%lld",&a[i]);
        a[i]%=mod;
    }
    for(re int i=1,u,v;i<=n-1;i++) {
        scanf("%lld%lld",&u,&v);
        qian(u,v);
        qian(v,u);
    }
    dfs1(root,0);
    dfs2(root,root);
    build(1,1,n);
    for(re int i=1,op,x,y,z;i<=m;i++) {
        scanf("%lld%lld",&op,&x);
        if(op==1) {
            scanf("%lld%lld",&y,&z);    
            update1(x,y,z);
        }
        else if(op==2) {
            scanf("%lld",&y);
            printf("%lld\n",query1(x,y));
        }
        else if(op==3) {
            scanf("%lld",&z);
            update2(x,z);
        }
        else {
            printf("%lld\n",query2(x));
        }
    }
    return 0;
}

后记

关于改边和查边的问题。

对于一条边，是连着一个父亲和一个儿子的。将控制这条边的权力（边权）交给儿子。

例题

若只修改两点间的边，注意不要修改 \mathrm{LCA} 的“点权”。

查询时只需要判断两个点哪个是儿子即可。

部分代码：

il void update(re int u,re int v) {
    while(top[u]!=top[v]) {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        modify(1,1,n,id[top[u]],id[u]);
        u=f[top[u]]; 
    }
    if(dep[u]>dep[v]) swap(u,v);
    modify(1,1,n,id[u]+1,id[v]);
}

    for(re int i=1,op,u,v;i<=m;i++) {
        scanf("\n%c%d%d",&op,&u,&v);
        if(op=='P') {
            update(u,v);
        }
        else {
            printf("%d\n",query(1,1,n,id[u]>id[v]?id[u]:id[v]));
        }
    }