首页 > 其他 > 详细

树链剖分

时间：2019-05-28 13:51:49      阅读：83      评论：0      收藏：0      [点我收藏+]

树链剖分

问题

  • 将树上x到y最短路径上所有结点的值都加上z
    • 可以用树上差分，cf[x]+=z ; cf[y]+=z; cf[lac(x,y)] -= z; cf[fa[lca(x,y)]] -= z;
  • 求树上从x到y结点最短路径的点权和或者边长和
    • dist = dis[x] + dis[y] - 2*dis[lac(x,y)],dis[x]代表结点x到root的距离，可以通过dfs预处理出来。
  • 求树上以结点x为根节点的子树所有点权之和

    • 可以用dfs序得到每个顶点的进站时间和出站时间，构造相应的点权序列order，对该序列建立线段树，查询结点x的子树点权和即查询order[in[u]]到order[out[u]]这个区间的和，由于该区间内所有顶点均出现两次所以结果除以2

    • 还有一种比较巧妙的做法是处理出每个结点的子树size，这样只需要处理出进栈序列就可以了，原理是这个子树的序号必然是连续的且子树根节点序号最小。查询时返回order[in[u]]到order[in[u]+size[u]-1]这个区间的和即可。

  • 将树上以节点x为根的子树中所有结点权值加z
    • 同理可以使用上面的方法，只不过把区间查询变为区间修改
  • 以上四种若结合起来用树链剖分比较容易

核心代码

  • 变量声明

    //链式前向星
int head[maxn];
int cnt;
struct edge{
  int v,w,nxt;
}edge[maxn<<1];

//树链相关
int siz[maxn];//子树大小 
int top[maxn];//重链顶端 
int son[maxn];//重儿子 
int dep[maxn];//结点深度 
int fa[maxn];//结点父亲 
int idx[maxn];//dfs序号对应结点 
int rk[maxn];//结点对应dfs序号 
int dfn;//dfs时序 

//线段树相关
int s[maxn<<2],e[maxn<<2];//区间左右端点 
ll sum[maxn<<2];//区间和
int lazy[maxn<<2]; //懒标记 

//权值保存
int a[maxn];//dfs序重新编号后的点权值数组 
int b[maxn];//原树的各点权值数组
  • 线段树，作用是维护把树处理出来的链，可区间修改区间查询
  • dfs序列构造
    • 链式前向星构图

    • 处理size father depth son数组

      //处理出size fa dep数组  son数组根据siz确定 
void dfs1(int u, int f, int d){
    dep[u] = d;
    fa[u] = f;
    siz[u] = 1;
    for(int i=head[u]; i ; i=edge[i].nxt){
        int v = edge[i].v;  
        if(v == f) continue;
        dfs1(v , u, d+1);
        siz[u] += siz[v];
        if(!son[u] || siz[son[u]] < siz[v]) son[u] = v;
    }   
}

    • 处理top idx rk数组(rk有时可以不需要)

      //处理出top idx rk数组 
void dfs2(int u, int t){
    top[u] = t;
    idx[u] = ++dfn;
    a[dfn] = b[u];//把u结点的权值重新赋值到dfs序列中
    rk[dfn] = u; 
    if(!son[u]) return ;//如果没有重儿子则返回
    dfs2(son[u] , t);//同一条重链上的结点拥有同一个top 
    for(int i=head[u]; i; i=edge[i].nxt){
        int v = edge[i].v;
        if(v != son[u] && v != fa[u]){ //如果当前结点不是重儿子 则其top等于自己 
            dfs2( v , v ); 
        }
    } 
}

    • 查询路径点权和

      ll queryRange(int x, int y){
    ll ans = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x , y);
        ans += query(1, idx[top[x]] , idx[x]);
        ans %= p;
        x = fa[top[x]];
    }

    //若x ,y不在同一点则还需要把这一条重链的点权加上 
    if(dep[x] > dep[y]) swap(x , y);
    ans += query(1 , idx[x] , idx[y]);
    ans %= p;
    return ans; 
}

    • 修改路径点权

      void updateRange(int x, int y, int k){
k %= p;
while(top[x] != top[y]){
    if(dep[top[x]] < dep[top[y]]) swap(x , y);
    update(1, idx[top[x]] , idx[x], k);
    x = fa[top[x]];
}

//若x ,y不在同一点则还需要把这一条重链的点权加上 
if(dep[x] > dep[y]) swap(x , y);

//由于x的深度小于y 而x,y又处于同一条链上 所以idx[x] < idx[y] 
update(1 , idx[x] , idx[y] , k);
}

    • 子树操作

      //关键点是子树结点在dfs序列中必然连续
ll querySon(int x){
    return query(1 , idx[x] , idx[x] + siz[x] - 1);
} 

void updateSon(int x ,int k){
    update(1 , idx[x] , idx[x] + siz[x] - 1, k);
}

例题

P3384 【模板】树链剖分

  • 思路：树链剖分模板

    #include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;

int n,m,r;//顶点数 操作个数 根节点  
int p ; //模数
//链式前向星建图 
int head[maxn];
int cnt;
struct edge{
    int v,w,nxt;
}edge[maxn<<1];

void addEdge(int u, int v){
    edge[++cnt].v = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

int siz[maxn];//子树大小 
int top[maxn];//重链顶端 
int son[maxn];//重儿子 
int dep[maxn];//结点深度 
int fa[maxn];//结点父亲 
int idx[maxn];//dfs序号对应结点 
int rk[maxn];//结点对应dfs序号 
int dfn;//dfs时序 
int s[maxn<<2],e[maxn<<2];//区间左右端点 
ll sum[maxn<<2];//区间和
int lazy[maxn<<2]; //懒标记 

int a[maxn];//原树的点权值数组
int b[maxn];//重新编号后的点权值数组 

void init(){
    memset(head , 0 ,sizeof head);
    memset(son , 0 ,sizeof son);
    cnt = 0;
    dfn = 0;
}
//处理出size fa dep数组  son数组根据siz确定 
void dfs1(int u, int f, int d){
    dep[u] = d;
    fa[u] = f;
    siz[u] = 1;
    for(int i=head[u]; i ; i=edge[i].nxt){
        int v = edge[i].v;  
        if(v == f) continue;
        dfs1(v , u, d+1);
        siz[u] += siz[v];
        if(!son[u] || siz[son[u]] < siz[v]) son[u] = v;
    }

} 
//处理出top idx rk数组 
void dfs2(int u, int t){
    top[u] = t;
    idx[u] = ++dfn;
    a[dfn] = b[u];//把u结点的权值重新赋值到dfs序列中
    rk[dfn] = u; 
    if(!son[u]) return ;//如果没有重儿子则返回
    dfs2(son[u] , t);//同一条重链上的结点拥有同一个top 
    for(int i=head[u]; i; i=edge[i].nxt){
        int v = edge[i].v;
        if(v != son[u] && v != fa[u]){ //如果当前结点不是重儿子 则其top等于自己 
            dfs2( v , v ); 
        }
    } 
}


void pushUp(int rt){
    sum[rt] = (sum[rt<<1] + sum[rt<<1|1]) % p;
}
void build(int rt, int l , int r){
    s[rt] = l, e[rt] = r;
    lazy[rt] = 0;
    if(l == r){
        sum[rt] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(rt<<1 , l , mid);
    build(rt<<1|1, mid+1, r);
    pushUp(rt);
} 

void pushDown(int rt){
    if(lazy[rt] != 0 && s[rt] != e[rt]){
        sum[rt<<1] += lazy[rt] * (e[rt<<1] - s[rt<<1] + 1);
        sum[rt<<1|1] += lazy[rt] * (e[rt<<1|1] - s[rt<<1|1] + 1) ;

        sum[rt<<1] %= p;
        sum[rt<<1|1] %= p;

        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];

        lazy[rt<<1] %= p;
        lazy[rt<<1|1] %= p;

        lazy[rt] = 0;
    }

}

void update(int rt, int l, int r, int val){
    if(s[rt] == l && e[rt] == r){
        sum[rt] += val*(e[rt] - s[rt] + 1);
        sum[rt] %= p;
        lazy[rt] += val;
        lazy[rt] %= p;
        return ;
    }

    pushDown(rt);
    int mid = (s[rt] + e[rt]) >> 1;
    if(l > mid)    update(rt<<1|1, l , r , val);
    else if(r <= mid) update(rt<<1, l , r, val);
    else{
        update(rt<<1, l , mid, val);
        update(rt<<1|1, mid+1, r, val);
    }
    pushUp(rt);
}

ll query(int rt, int l, int r){
    //ll ans = 0;
    if(s[rt] == l && e[rt] == r)    return sum[rt];
    pushDown(rt);
    int mid = (s[rt] + e[rt]) >> 1;
    if(l > mid) return query(rt<<1|1,l,r);
    else if(r <= mid) return query(rt<<1,l,r);
    else return (query(rt<<1,l,mid) + query(rt<<1|1, mid+1,r)) % p;
}


ll queryRange(int x, int y){
    ll ans = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x , y);
        ans += query(1, idx[top[x]] , idx[x]);
        ans %= p;
        x = fa[top[x]];
    }

    //若x ,y不在同一点则还需要把这一条重链的点权加上 
    if(dep[x] > dep[y]) swap(x , y);
    ans += query(1 , idx[x] , idx[y]);
    ans %= p;
    return ans; 
}

void updateRange(int x, int y, int k){
    k %= p;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x , y);
        update(1, idx[top[x]] , idx[x], k);
        x = fa[top[x]];
    }

    //若x ,y不在同一点则还需要把这一条重链的点权加上 
    if(dep[x] > dep[y]) swap(x , y);

    //由于x的深度小于y 而x,y又处于同一条链上 所以idx[x] < idx[y] 
    update(1 , idx[x] , idx[y] , k);
}

ll querySon(int x){
    return query(1 , idx[x] , idx[x] + siz[x] - 1);
} 

void updateSon(int x ,int k){
    update(1 , idx[x] , idx[x] + siz[x] - 1, k);
}

int main(){
    int u,v,w,op;
    while(scanf("%d %d %d %d",&n,&m,&r,&p) != EOF){
        init();
        //读入点权 
        for(int i=1; i<=n; i++) scanf("%d",&b[i]);
        //建图 
        for(int i=1; i<n; i++){
            scanf("%d %d", &u, &v);
            addEdge(u , v);
            addEdge(v , u); 
        }
        dfs1(r , 0, 1);
        dfs2(r , r);
        build(1 , 1, n);
        for(int i=1; i<=m; i++){
            scanf("%d" ,&op);
            if(op == 1){
                scanf("%d %d %d", &u,&v,&w);
                updateRange(u , v, w);
            }
            else if(op == 2){
                scanf("%d %d", &u, &v);
                printf("%lld\n",queryRange(u , v));
            }
            else if(op == 3){
                scanf("%d %d", &u, &w);
                updateSon(u ,w);
            }
            else{
                scanf("%d",&u);
                printf("%lld\n",querySon(u));
            }
        }
    } 
    return 0;
}

BZOJ4034

  • 题意：树上单点修改，子树修改， 子树查询

  • 思路 ： 树链剖分模板题，或者dfs序结合线段树

    #include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;

int n,m;//顶点数 操作个数 
//链式前向星建图 
int head[maxn];
int cnt;
struct edge{
    int v,w,nxt;
}edge[maxn<<1];

void addEdge(int u, int v){
    edge[++cnt].v = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

int siz[maxn];//子树大小 
int top[maxn];//重链顶端 
int son[maxn];//重儿子 
int dep[maxn];//结点深度 
int fa[maxn];//结点父亲 
int idx[maxn];//dfs序号对应结点 
int rk[maxn];//结点对应dfs序号 
int dfn;//dfs时序 
int s[maxn<<2],e[maxn<<2];//区间左右端点 
ll sum[maxn<<2];//区间和
ll lazy[maxn<<2]; //懒标记 

int a[maxn];//原树的点权值数组
int b[maxn];//重新编号后的点权值数组 

void init(){
    memset(head , 0 ,sizeof head);
    memset(son , 0 ,sizeof son);
    cnt = 0;
    dfn = 0;
}
//处理出size fa dep数组  son数组根据siz确定 
void dfs1(int u, int f, int d){
    dep[u] = d;
    fa[u] = f;
    siz[u] = 1;
    for(int i=head[u]; i ; i=edge[i].nxt){
        int v = edge[i].v;  
        if(v == f) continue;
        dfs1(v , u, d+1);
        siz[u] += siz[v];
        if(!son[u] || siz[son[u]] < siz[v]) son[u] = v;
    }

} 
//处理出top idx rk数组 
void dfs2(int u, int t){
    top[u] = t;
    idx[u] = ++dfn;
    a[dfn] = b[u];//把u结点的权值重新赋值到dfs序列中
    rk[dfn] = u; 
    if(!son[u]) return ;//如果没有重儿子则返回
    dfs2(son[u] , t);//同一条重链上的结点拥有同一个top 
    for(int i=head[u]; i; i=edge[i].nxt){
        int v = edge[i].v;
        if(v != son[u] && v != fa[u]){ //如果当前结点不是重儿子 则其top等于自己 
            dfs2( v , v ); 
        }
    } 
}


void pushUp(int rt){
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int rt, int l , int r){
    s[rt] = l, e[rt] = r;
    lazy[rt] = 0;
    if(l == r){
        sum[rt] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(rt<<1 , l , mid);
    build(rt<<1|1, mid+1, r);
    pushUp(rt);
} 

void pushDown(int rt){
    if(lazy[rt] != 0 && s[rt] != e[rt]){
        sum[rt<<1] += lazy[rt] * (e[rt<<1] - s[rt<<1] + 1);
        sum[rt<<1|1] += lazy[rt] * (e[rt<<1|1] - s[rt<<1|1] + 1) ;

        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];

        lazy[rt] = 0;
    }

}

void update(int rt, int l, int r, int val){
    if(s[rt] == l && e[rt] == r){
        sum[rt] += 1LL*val*(e[rt] - s[rt] + 1);
        lazy[rt] += 1LL*val;
        return ;
    }

    pushDown(rt);
    int mid = (s[rt] + e[rt]) >> 1;
    if(l > mid)    update(rt<<1|1, l , r , val);
    else if(r <= mid) update(rt<<1, l , r, val);
    else{
        update(rt<<1, l , mid, val);
        update(rt<<1|1, mid+1, r, val);
    }
    pushUp(rt);
}

ll query(int rt, int l, int r){
    //ll ans = 0;
    if(s[rt] == l && e[rt] == r)    return sum[rt];
    pushDown(rt);
    int mid = (s[rt] + e[rt]) >> 1;
    if(l > mid) return query(rt<<1|1,l,r);
    else if(r <= mid) return query(rt<<1,l,r);
    else return query(rt<<1,l,mid) + query(rt<<1|1, mid+1,r);
}


ll queryRange(int x, int y){
    ll ans = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x , y);
        ans += query(1, idx[top[x]] , idx[x]);
        x = fa[top[x]];
    }

    //若x ,y不在同一点则还需要把这一条重链的点权加上 
    if(dep[x] > dep[y]) swap(x , y);
    ans += query(1 , idx[x] , idx[y]);
    return ans; 
}

void updateRange(int x, int y, int k){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x , y);
        update(1, idx[top[x]] , idx[x], k);
        x = fa[top[x]];
    }

    //若x ,y不在同一点则还需要把这一条重链的点权加上 
    if(dep[x] > dep[y]) swap(x , y);

    //由于x的深度小于y 而x,y又处于同一条链上 所以idx[x] < idx[y] 
    update(1 , idx[x] , idx[y] , k);
}


void updateSon(int x ,int k){
    update(1 , idx[x] , idx[x] + siz[x] - 1, k);
}

int main(){
    int u,v,w,op;
    while(scanf("%d %d",&n,&m) != EOF){
        init();
        //读入点权 
        for(int i=1; i<=n; i++) scanf("%d",&b[i]);
        //建图 
        for(int i=1; i<n; i++){
            scanf("%d %d", &u, &v);
            addEdge(u , v);
            addEdge(v , u); 
        }
        dfs1(1 , 0, 1);
        dfs2(1 , 1);
        build(1 , 1, n);
        for(int i=1; i<=m; i++){
            scanf("%d" ,&op);
            if(op == 1){
                scanf("%d %d", &u ,&w);
                updateRange(u,u,w);
            }
            else if(op == 2){
                scanf("%d %d", &u, &w);
                updateSon(u , w);
            }
            else if(op == 3){
                scanf("%d", &u);
                printf("%lld\n",queryRange(1,u));
            }

        }
    } 
    return 0;
}

树链剖分求LCA

  • 核心思想:通过top数组和father数组将x,y结点调到一条重链上，然后返回x,y深度较小的一个

    #include<iostream>
#include<cstring>
using namespace std;
const int maxn = 5e5+10;

int n,m,s;//顶点数 询问次数 树根 

//链式前向星建图 
int head[maxn];
int cnt;
struct edge{
    int v,w,nxt;
}edge[maxn<<1];

void addEdge(int u, int v){
    edge[++cnt].v = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

int siz[maxn];//子树大小 
int top[maxn];//重链顶端 
int son[maxn];//重儿子 
int dep[maxn];//结点深度 
int fa[maxn];//结点父亲 
int idx[maxn];//dfs序号对应结点 
int rk[maxn];//结点对应dfs序号 
int dfn;//dfs时序 

void init(){
    memset(head , 0 ,sizeof head);
    memset(son , 0 ,sizeof son);
    cnt = 0;
    dfn = 0;
}
//处理出size fa dep数组  son数组根据siz确定 
void dfs1(int u, int f, int d){
    dep[u] = d;
    fa[u] = f;
    siz[u] = 1;
    for(int i=head[u]; i ; i=edge[i].nxt){
        int v = edge[i].v;  
        if(v == f) continue;
        dfs1(v , u, d+1);
        siz[u] += siz[v];
        if(!son[u] || siz[son[u]] < siz[v]) son[u] = v;
    }

} 
//处理出top idx rk数组 
void dfs2(int u, int t){
    top[u] = t;
    idx[u] = ++dfn;
    rk[dfn] = u;
    if(!son[u]) return ;//如果没有重儿子则返回
    dfs2(son[u] , t);//同一条重链上的结点拥有同一个top 
    for(int i=head[u]; i; i=edge[i].nxt){
        int v = edge[i].v;
        if(v != son[u] && v != fa[u]){ //如果当前结点不是重儿子 则其top等于自己 
            dfs2( v , v ); 
        }
    } 
}

int LCA(int x, int y){
    while(top[x] != top[y]){
        if(dep[top[x]] > dep[top[y]]){
            x = fa[top[x]];
        }
        else{
            y = fa[top[y]];
        }
    }
    return  dep[x] < dep[y] ? x : y;
} 

int main(){
    int u,v;
    while(scanf("%d%d%d",&n,&m,&s) != EOF){
        init();
        for(int i=1; i<n; i++){
            scanf("%d %d", &u, &v);
            addEdge(u , v);
            addEdge(v , u); 
        }
        dfs1(s , 0, 1);
        dfs2(s , s);
        for(int i=1; i<=m; i++){
            scanf("%d %d", &u, &v);
            printf("%d\n",LCA(u,v));
        }
    } 
}

树链剖分

原文：https://www.cnblogs.com/czsharecode/p/10936701.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！