Chlience

【算法】灰常简陋的树链剖分总结
树剖想必各位大佬早已经烂熟于心此篇博客大部分将 灌水 写写自己在学习树链剖分时对于各部分的理解树链剖分是一种将树转...
扫描右侧二维码阅读全文
13
2018/10

【算法】灰常简陋的树链剖分总结

树剖想必各位大佬早已经烂熟于心
此篇博客大部分将 灌水 写写自己在学习树链剖分时对于各部分的理解

树链剖分是一种将树转化为链进行维护的数据结构
也可以说是将点按一定的顺序放在序列中,使得修改两个点之间的路径时将一段非连续序列转化为 多个连续区间,用线段树分别进行修改

如何进行排列?

一般来说,最有可能同时修改的点我们尽量将其放在一起
对于每个点定义其子节点中子树大小最大的为其 重儿子
其他子节点为 轻儿子 ,其连边分别为 重边轻边

显然,非叶子节点都有重边。将连续的重边链接成一条链,那就成为了重链,串起了一堆重儿子

我们就将这些重链上的点放入线段树中维护,只需保证其在一段连续的序列中并且按照深度递增即可
剩下的轻边轻儿子其实想放哪儿都行

可以证明两个点之间不会超过$\log n$条重链,$\log n$条轻链

两个点通过重链,轻链不断向上跳,每次跳直接跳到当前链深度最小的点,直至相遇

emm,很简单的就不多讲了

HDU 3996

#include <bits/stdc++.h>
using namespace std;
typedef vector <int> ve;
const int N = 50010;
#define L (x << 1)
#define R (x << 1 | 1) 
#define mid ((l + r) >> 1)
ve e[N];
int n , m , p;
int a[N];
int F[N] , num[N];
int siz[N] , dep[N] , son[N] , fa[N];
int top[N] , pos[N] , fps[N] , sz;
int sum[N << 2] , tag[N << 2];

char str[10];
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = -1; ch = getchar();}
    while(ch >= '0' &&ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int find(int x) {return x == F[x] ? F[x] : F[x] = find(F[x]);}
void merge(int u , int v) {
    u = find(u); v = find(v);
    if(u == v) return;
    if(num[u] > num[v]) swap(u , v);
    F[u] = v;
    num[v] += num[u]; num[u] = 0;
}
void dfs1(int now , int f , int deep) {
    fa[now] = f; son[now] = -1; siz[now] = 1; dep[now] = deep;
    for(ve :: iterator iter = e[now].begin() ; iter != e[now].end() ; iter ++) {
        if(*iter == f) continue;
        dfs1(*iter , now , deep + 1);
        siz[now] += siz[*iter];
        if(son[now] == -1 || siz[*iter] > siz[son[now]]) son[now] = *iter;
    }
}
void dfs2(int now , int _top) {
    top[now] = _top;
    pos[now] = ++ sz;
    fps[sz] = now;
    if(son[now] != -1) dfs2(son[now] , _top);
    for(ve :: iterator iter = e[now].begin() ; iter != e[now].end() ; iter ++) {
        if(*iter == fa[now] || *iter == son[now]) continue;
        dfs2(*iter , *iter);
    }
}
void build(int x , int l , int r) {
    if(l == r) sum[x] = a[fps[l]];
    else {build(L , l , mid); build(R , mid + 1 , r);}
}
int query(int x , int l , int r , int k) {
    if(l == r) return sum[x] + tag[x];
    if(k <= mid) return tag[x] + query(L , l , mid , k);
    else return tag[x] + query(R , mid + 1 , r , k); 
}
void change(int x , int l , int r , int ll , int rr , int k) {
    if(ll > rr) return;
    if(l == ll && r == rr) {tag[x] += k; return;}
    change(L , l , mid , ll , min(mid , rr) , k);
    change(R , mid + 1 , r , max(mid + 1 , ll) , rr , k);
}
void Change(int u , int v , int k) {
    int f1 = top[u] , f2 = top[v];
    while(f1 != f2) {
        if(dep[f1] < dep[f2]) {swap(f1 , f2); swap(u , v);} 
        change(1 , 1 , n , pos[f1] , pos[u] , k);
        u = fa[f1];
        f1 = top[u];
    }
    if(dep[u] > dep[v]) swap(u , v);
    change(1 , 1 , n , pos[u] , pos[v] , k);
}
void clear() {
    memset(sum , 0 , sizeof(sum));
    memset(tag , 0 , sizeof(tag));
    memset(siz , 0 , sizeof(siz));
    memset(dep , 0 , sizeof(dep));
    memset(son , 0 , sizeof(son));
    memset(fa , 0 , sizeof(fa));
    memset(top , 0 , sizeof(top));
    memset(pos , 0 , sizeof(pos));
    memset(fps , 0 , sizeof(fps));
    memset(e , 0 , sizeof(e));
    sz = 0;
}
int main() {
    while(~scanf("%d" , &n)) {
        clear();
        m = read(); p = read();
        for(int i = 1 ; i <= n ; ++ i) {a[i] = read(); F[i] = i; num[i] = 1;}
        for(int i = 1 ; i <= m ; ++ i) {
            int u = read() , v = read();
            e[u].push_back(v);
            e[v].push_back(u);
            merge(u , v);
        }
        for(int i = 1 ; i <= n ; ++ i)
            if(F[i] == i) {
                dfs1(i , 0 , 1);
                dfs2(i , i);
            }
        build(1 , 1 , n);
        for(int i = 1 ; i <= p ; ++ i) {
            scanf("%s" , str);
            if(str[0] == 'I') {
                int c1 = read() , c2 = read() , q = read();
                Change(c1 , c2 , q);
            }else if(str[0] == 'D') {
                int c1 = read() , c2 = read() , q = read();
                Change(c1 , c2 , - q);
            }else printf("%d\n" , query(1 , 1 , n , pos[read()]));
        }
    }
    return 0;
}
Last modification:October 13th, 2018 at 10:42 pm

Leave a Comment