8.4 树链剖分

柔情只为你懂 2021-10-18 08:52 337阅读 0赞

详解：https://www.cnblogs.com/ivanovcraft/p/9019090.html

树链剖分的本质是序

以尽量走重链为序，使一棵树的结点尽量集中地分解成较少的链，而链作为连续的数据结构是易于维护的

剖分的过程有两遍dfs ：

dfs1：找出重结点 ，确立各个点的深度 ，这个过程可以确定：sz\[i\] ,dep\[i\] ,fa\[i\] ,son\[i\]

void dfs1( int u ,int f ){
        sz[u] = 1;
        for( int i = head[u]; i ;i = edge[i].next ){
            int v = edge[i].to;
            if( v == f )continue;
            dep[v] = dep[u] + 1;
            fa[v] = u;
            dfs1( v ,u );
            sz[u] += sz[v];
            if( sz[v] >sz[ son[u] ] )son[u] = v;
        }
    }

dfs2：将重结点链接成链（找出top\[i\]），并以这个链接的顺序作为将链存在数组中的顺序（dfn\[i\]），这个过程可以确定：dfn ，top ，rnk

void dfs2( int u ,int t ){
        dfn[u] = ++tot;
        top[u] = t;
        rnk[tot] = u;
        if( son[u] )dfs2( son[u] ,t );
        for( int i = head[u] ;i ;i = edge[i].next ){
            int v = edge[i].to;
            if( v!= fa[u] && v!= son[u] )dfs2(v,v);
        }
    }

剖分后就可以利用线段树，树状数组等数据结构对分解后的链进行维护，给定两个节点x,y，进行它们之间的更新和查询操作，这个过程是：

1.如果x，y在一条重链上（ top\[x\]==top\[y\] ）,则可以直接利用数据结构对x到y这一段连续的链进行直接操作

2.如果x，y不在一条重链上（ top\[x\] != top\[y\] ），找出较深的结点（dep\[fx\]>dep\[fy\]）x，先将x到fx这一小段进行操作，再令x向其重链之上的父节点转移

重复这一过程，直到完成x到y之间完整路径的操作

这一过程也是寻找x，y LCA 的过程

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

int c_query( int x ,int y ){
        int fx = top[x] ,fy = top[y];
        int ans = 0;
        while( fx != fy ){
            if( dep[fx] < dep[fy] )swap(x ,y) ,swap(fx ,fy);
            ans += query( 1 ,dfn[fx] ,dfn[x] );
            x = fa[x] ,fx = top[x];
        }
        if( x==y )return ans;
        if( dfn[x] > dfn[y] )swap( x ,y );
        if(dfn[x] != dfn[y])ans += query( 1 ,dfn[son[x]] ,dfn[y] );
        return ans ;
    }

线段树： 网上关于树链剖分的代码线段树大多都是以结构体形式写的：

struct Tree{
        int left ,right;
        int t ,lazy;
    }tree[N<<2];

难道这样更快？不懂（可能这个问题我永远也不会搞懂

模板题：HDU 3966 *Aragorn's* *Story*

区间修改，单点查询

这个我线段树没用结构体写也过了

#include<bits/stdc++.h>
    
    #define fi first
    #define se second
    #define rep( i ,x ,y ) for( int i= x; i<= y ;i++ )
    #define reb( i ,y ,x ) for( int i= y; i>= x ;i-- )
    #define mem( a ,x ) memset( a ,x ,sizeof(a))
    #define lson  pos<<1 ,l ,m
    #define rson  pos<<1|1 ,m+1 ,r
    using namespace std;
    
    typedef long long ll;
    typedef long double ld;
    typedef pair<int ,int> pii;
    typedef pair<ll ,ll> pll;
    typedef pair<string ,int> psi;
    
    const int inf = 0x3f3f3f3f;
    const int N = 50005;
    const int M = 1000005;
    
    struct Edge{
        int next ,to;
    }edge[N<<2];
    int sz[N] ,top[N] ,son[N] ,dep[N];
    int fa[N] ,dfn[N] ,rnk[N];
    int m ,n ,q ,tot = 0 ,cnt = 0 ,k;
    int head[N] ;
    ll val[N<<2] ,tree[N<<4] ,lazy[N<<4];
    
    //线段树部分
    void build( int pos ,int l ,int r ){
        if( l== r){
            tree[pos] = val[ rnk[l] ];
            return;
        }
    
        int m = (l+r)>>1;
        build ( rson );
        build ( lson );
        tree[pos] = tree[pos<<1]+tree[pos<<1|1];
        return;
    }
    
    void push_down( int pos ){
        int lc = pos<<1 ,rc = pos<<1|1 ;
        tree[lc] += lazy[pos];
        tree[rc] += lazy[pos];
        lazy[lc] += lazy[pos];
        lazy[rc] += lazy[pos];
        lazy[pos] = 0;
        return;
    }
    
    void updata( int pos ,int  l, int r ,int L ,int R ,int k ){
        //cout<<" updata "<<l<<" "<<r<<" "<<L<<" "<<R <<" "<<k<<endl;
        if( L<=l && r<=R ){
            lazy[pos] += k;
            tree[pos] += k;
            return;
        }
    
        int m = ( l+r )>>1;
        if( L <= m )updata( lson ,L ,R ,k);
        if( R > m )updata( rson ,L ,R ,k);
        tree[pos] = tree[pos>>1] + tree[pos>>1|1];
        return;
    }
    
    ll query( int pos ,int l ,int r ,int L ,int R ){
        //cout<<" query "<<l<<" "<<r<<" " <<L <<" "<<R<<endl;
        if( L<=l && r <= R ) return tree[pos];
    
        ll ans=0;
        push_down( pos );
    
        int m =( l+r )>>1;
        if( L <=m )ans += query( lson ,L ,R );
        if( R > m )ans += query( rson ,L ,R );
        return ans;
    }
    
    //树链剖分部分 --dfs1 ,dfs2 ,query ,updata
    void dfs1( int u ,int rt ,int d ){
        //cout<<" dfs1 "<<u<<" "<<rt<<" dep "<<d<<endl;
        dep[u] = d;
        fa[u] = rt;
        sz[u] = 1;
    
        for( int i = head[u]; i ;i = edge[i].next ){
             int v =edge[i] .to;
             if( v == fa[u] )continue;
             dfs1( v ,u ,d+1 );
             sz[u] += sz[v];
             if( son[u] == 0 || sz[v] >sz[ son[u]]){
                 son[u] = v;
             }
        }
        return ;
    }
    
    void dfs2( int u ,int t ){
        // u : now t :top
        //cout<<" dfs2 "<<u<<" "<<t<<" son "<<son[u]<<endl;
        top[u] = t;
        dfn[u] = ++cnt;
        rnk[cnt] = u;
    
        if( !son[u] ){
            return ;
        }
        dfs2( son[u] ,t );
        for( int i = head[u]; i ; i = edge[i].next ){
            int v=  edge[i].to;
            if( v == son[u] || v == fa[u] )continue;
            dfs2( v, v );
        }
    }
    
    ll query_path( int x ,int y){
       ll ans = 0;
       int fx = top[x] ,fy = top[y];
       //cout<<" query_p "<<x <<" "<<y<<" "<<fx<<" "<<fy<<endl;
       while( fx != fy ){
              if(dep[fx] >= dep[fy] ){
                    ans += query( 1 ,1 ,n ,dfn[fx] ,dfn[x] );
                    x = fa[fx] ;
              }  else {
                    ans += query( 1 ,1 ,n ,dfn[fy] ,dfn[y] );
                    y = fa[fy];
              }
              fx = top[x] ,fy = top[y];
       }
    
       if(x != y ){
               if( dfn[x] < dfn[y] ){
                   ans += query(1 ,1 ,n,dfn[x] ,dfn[y] );
               } else {
                   ans += query(1 ,1 ,n,dfn[y] ,dfn[x] );
               }
       } else ans += query( 1 ,1 ,n,dfn[x] ,dfn[y] );
       return ans;
    }
    
    void updata_path( int x ,int y ,int z ){
        //cout<<x<<y<<z<<endl;
        int fx = top[x] ,fy = top[y];
        //cout<<" updata_p "<<x <<" "<<y<<" "<<fx<<" "<<fy<<endl;
        while( fx != fy ){
            if( dep[fx] >= dep[fy] ){
                updata( 1 ,1 ,n ,dfn[fx] ,dfn[x] ,z);
                x = fa[fx];
            } else {
                updata( 1 ,1 ,n ,dfn[fy] ,dfn[y] ,z);
                y = fa[fy];
            }
            fx = top[x] ,fy = top[y];
        }
    
        if( x!=y ){
            if( dfn[x] < dfn[y] )updata( 1 ,1 ,n ,dfn[x] ,dfn[y] ,z );
            else updata( 1 ,1 ,n ,dfn[y] ,dfn[x] ,z );
        } else updata( 1 ,1 , n, dfn[x] ,dfn[y] ,z);
    }
    
    
    int main( ){
        while( ~ scanf("%d%d%d" ,&n ,&m ,&q) ){
            cnt = tot = 0;
            mem( son ,0 );
            mem( tree ,0);
            mem( lazy ,0);
    
            rep( i ,1 ,n )scanf("%lld" ,&val[i] ) ,head[i] = edge[i].next = 0;
            int l ,r;
            while( m-- ){
                scanf("%d%d" ,&l ,&r );
                edge[++tot].next = head[l];
                edge[tot].to = r;
                head[l] = tot;
    
                edge[++tot].next = head[r];
                edge[tot].to = l;
                head[r] = tot;
            }
    
            dfs1( 1 ,1 ,0 );
            dfs2( 1 ,1 );
            build(1, 1 ,n );
            char op;
            while ( q--){
                //cout<<q<<endl;
    
                cin>>op;
                if( op == 'I' ){
                    scanf("%d%d%d" ,&l ,&r ,&k);
                    updata_path( l ,r ,k );
                }
                if( op == 'Q' ){
                    scanf("%d" ,&l );
                    printf("%lld\n" ,query(1 ,1 ,n ,dfn[ l ] ,dfn[ l ] ) );
                }
                if( op == 'D' ){
                    scanf("%d%d%d" ,&l ,&r ,&k);
                    //cout<<l<<" "<<r<<" "<<k<<endl;
                    updata_path( l ,r ,-k );
                }
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/-ifrush/p/11298274.html