树链剖分


By Tak3n

说明

Tak3n

树链剖分解决在树上进行任意两点间的一类路径更新和路径查询的问题。大体分为点权型和边权型两种。该模板以更新点,单点更新,区间查询,求和 为基础,其他种类在后面补充。

Manyfun

示例题目都是使用Tak3n的模版做的,模版很完善,但是细节要注意。分清楚边权型题目和点权型题目的建图区别,线段树方面要注意是使用RMQ/区间更新/单点更新的板子。当边权型题目最后是找son[u]v,详解请见本人SPOJ-QTREE Query on a tree题解

推荐博客

树链剖分——starszys的博客

使用方法

  1. work(n)初始化,注意输入点权和输入树的先后关系,默认点下标从1开始,树根为1
  2. find(x,y) 求x,y路径上的点权和(或最值,可通过修改线段树得到)
  3. update(w[x],y,1,nodenum) 将x节点的权值更新为y

示例

  1. 点权,区间更新,单点/区间求和HDU 3966 Aragorn's Story
  2. 边权,单点更新,单点/区间求和POJ 2763 Housewife Wind
  3. 点权,单点更新,单点/区间求和LightOJ 1348 Aladdin and the Return Journey
  4. 边权,单点更新,区间求和FZU 2082 过路费
  5. 点权,单点更新,区间求和+RMQHYSBZ 1036 树的统计Count
  6. 边权,单点更新,区间RMQSPOJ-QTREE Query on a tree
  7. 点权+边权,区间更新,单点查询,数组维护HDU 5044 Tree
  8. 点权,单点更新,线段树变型HDU 5274 Dylans loves tree

模版

// 点权型 单点更新 区间查询
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int Vmax = 5*1e4 + 5;//点的数量
const int Emax =2*1e5+5;//边的数量 小于Vmax的两倍
namespace segment_tree{
    int sum[Vmax<<2],add[Vmax<<2];
    inline void pushup(int rt){
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    void update(int L,int c,int l,int r,int rt=1){
        if (L == l && l == r)
        {
            sum[rt] = c;
            return ;
        }
        int m = (l + r) >> 1;
        if (L <= m) update(L , c , lson);
        else update(L , c , rson);
        pushup(rt);
    }
    int query(int L,int R,int l,int r,int rt=1){
        if (L <= l && r <= R)
            return sum[rt];
        int m = (l + r) >> 1;
        int ret = 0;
        if (L <= m) ret+=query(L , R , lson);
        if (m < R) ret+=query(L , R , rson);
        return ret;
    }
}
namespace poufen{
    using namespace segment_tree;
    int siz[Vmax],son[Vmax],fa[Vmax],dep[Vmax],top[Vmax],w[Vmax];
    int nodenum;

    struct edge{
        int v,next;
    }e[Emax];
    int pre[Vmax],ecnt;
    inline void init(){
        memset(pre, -1, sizeof(pre));
        ecnt=0;
    }
    inline void add_(int u,int v){
        e[ecnt].v=v;
        e[ecnt].next=pre[u];
        pre[u]=ecnt++;
    }
    void dfs(int u){
        siz[u]=1;son[u]=0;//下标从1开始,son[0]初始为0
        for(int i=pre[u];~i;i=e[i].next)
        {
            int v=e[i].v;
            if(fa[u]!=v)
            {
                fa[v]=u;
                dep[v]=dep[u]+1;//初始根节点dep!!
                dfs(v);
                siz[u]+=siz[v];
                if(siz[v]>siz[son[u]])son[u]=v;
            }
        }
    }
    void build_tree(int u,int tp){
        top[u]=tp,w[u]=++nodenum;
        if(son[u])build_tree(son[u],tp);
        for(int i=pre[u];~i;i=e[i].next)
            if(e[i].v!=fa[u]&&e[i].v!=son[u])
                build_tree(e[i].v,e[i].v);
    }

    inline int find1(int u,int v){
        int ret=0;
        int f1=top[u],f2=top[v];
        while(f1!=f2)
        {
            if(dep[f1]<dep[f2])
                swap(f1,f2),swap(u,v);
            ret+=query(w[f1],w[u],1,nodenum);
            u=fa[f1];
            f1=top[u];
        }
        if(dep[u]>dep[v])swap(u,v);
        ret+=query(w[u],w[v],1,nodenum);
        return ret;
    }
    int a[Vmax],b[Vmax];
    int val[Vmax];//
    void work1(int n)
    {
        memset(siz, 0, sizeof(siz));
        memset(sum, 0, sizeof(sum));

        init();
        int root=1;
        fa[root]=nodenum=dep[root]=0;
        for(int i=1;i<=n;i++)
            scanf("%d",&val[i]);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a[i],&b[i]);
            add_(a[i],b[i]);
            add_(b[i],a[i]);
        }
        dfs(root);
        build_tree(root,root);
        for(int i=1;i<=n;i++)
            update(w[i],val[i],1,nodenum);
    }

}
using namespace poufen;

如果是更新边,find函数替换为以下函数。

边权型

inline int find2(int u,int v){
    int f1=top[u],f2=top[v],ret=0;
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2])
            swap(f1,f2),swap(u,v);
        ret+=query(w[f1],w[u],1,nodenum);
        u=fa[f1];
        f1=top[u];
    }
    if(u==v)return ret;
    if(dep[u]>dep[v])swap(u,v);
    return ret+=query(w[son[u]],w[v],1,nodenum);
}

如果是边权型,work函数替换为以下函数。

void work2(int n){
   memset(siz, 0, sizeof(siz));
   memset(sum, 0, sizeof(sum));

   init();
   int root=1;
   fa[root]=nodenum=dep[root]=0;
   for(int i=1;i<n;i++)
   {
       scanf("%d%d%d",&a[i],&b[i],&c[i]);
       add_(a[i],b[i]);
       add_(b[i],a[i]);
   }
   dfs(root);

   build_tree(root,root);

   for(int i=1;i<n;i++){
       int u = a[i];
       int v = b[i];
       if (dep[u] > dep[v]) {  //保证v是被指向的点,也就是深度较大的点
           swap(u, v);
           swap(a[i], b[i]);
       }
       update(w[v],c[i],1,nodenum);
   }
}

区间更新

点更新

如果是区间更新,update为upd(u,v,c)意为将u,v路径上的点权都+=c,注意将线段树模板修改成区间更新模板,直接改为c的操作可以修改线段树模板

inline void upd1(int u,int v,int c){
    int f1=top[u],f2=top[v];
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2])
            swap(f1,f2),swap(u,v);
        update(w[f1],w[u],c,1,nodenum);
        u=fa[f1];
        f1=top[u];
    }
    if(dep[u]>dep[v])swap(u,v);
    update(w[u],w[v],c,1,nodenum);
}
边更新

区间更新:upd2(u,v,c)意为将u,v路径上的边权+=c

inline void upd(int u,int v,int c){
    int f1=top[u],f2=top[v];
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2])
            swap(f1,f2),swap(u,v);
        update(w[f1],w[u],c,1,nodenum);
        u=fa[f1];
        f1=top[u];
    }
    if(u==v)return;
    if(dep[u]>dep[v])swap(u,v);
    update(w[son[u]],w[v],c,1,nodenum);
}

results matching ""

    No results matching ""