树链剖分（Heavy-Light Decomposition）

16-10-09 来源：[db:作者]

收藏我要投稿

一、概述

所谓树链剖分，就是把树上的路径进行重链、轻链的划分

它并不是一个复杂的算法或者数据结构，只是能把一棵树拆成链来处理而已

换句话说，树链剖分只是 xx 数据结构 / 算法在树上的推广

定义 size[v] 为以 v 为根节点的子树节点的个数，引入一些概念

重儿子（Preferred Child）：令 u 为 v 的儿子中 size 最大的节点，那么 u 就是 v 的重儿子，一个节点最多只能有一个重儿子
重(zhòng)边（Preferred Edge）：连接父亲节点和重儿子的边
重链（Preferred Path）：由重边及重边连接的节点构成的链

显然有如下性质：

如果 (v, u) 不为重边，则 size[u] * 2 < size[v]
从根节点到某一节点的路径上，重边和轻边的数量都不超过 logn 条

二、解决的问题

维护一棵树，支持下列操作：

链上求和

链上求最值

链上修改

子树修改

子树求和

换根

三、实现

1、首先进行如下定义

size[v] ：以 v 为根节点的子树节点的个数

depth[v] ：节点 v 的深度（根节点的深度为 1）

top[v] ：v 所在链的顶端节点

father[v] ：v 的父亲节点

son[v] ：v 的重儿子结点

id[v] ：v 在线段树中的位置（基于点的重编号）

key[pos] ：线段树 pos 位置上所存储的点（基于点的重编号）

2、分两次 dfs 进行剖分

第一次 dfs：

求出所有的节点的 size、depth、size、son、father

第二次 dfs：

求出所有节点的 top、id 以及线段树所有位置上的点

dfs 过程中保证重链各边在线段树中连续分布

对于非叶子节点 v，显然有 top[son[v]] = top[v]，对于 v 的轻儿子 u，有 top[u] = u

修改操作

（1）如果节点 u、v 不在同一条重链上，就不断修改至 u、v 处于同一条重链

（2）如果节点 u、v 在同一条重链上，直接进行修改

求和、求最值操作与修改操作类似

四

1、HDU 3966 Aragorn's Story

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define lson low, mid, _id<<1
#define rson mid+1, high, _id<<1|1
#define Left(_id) (_id<<1)
#define Right(_id) (_id<<1|1)

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair Pair;

const ull mod = 1e9 + 7;
const int INF = 0x7fffffff;
const int maxn = 5e4 + 10;

int N, M, Q, id_count, _u, _v, a, b, c;
int A[maxn], size[maxn], son[maxn], father[maxn], depth[maxn], id[maxn], key[maxn], top[maxn];
int head[maxn], to[2*maxn], Next[2*maxn], edge;
int tree[4*maxn], lazy[4*maxn];
char cmd[5];

void Init(void);
void add_edge(int u, int v);
void dfs_first(int u, int _father, int _depth);
void dfs_second(int u, int _top);
void build(int low, int high, int _id);
void update(int Left, int Right, int add, int low, int high, int _id);
void pushdown(int _id);
int query(int val, int low, int high, int _id);
void change(int u, int v, int add);

int main()
{
#ifdef __AiR_H
    freopen("in.txt", "r", stdin);
#endif // __AiR_H
    while (scanf("%d %d %d", &N, &M, &Q) != EOF) {
        Init();
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &A[i]);
        }
        for (int i = 1; i <= M; ++i) {
            scanf("%d %d", &_u, &_v);
            add_edge(_u, _v), add_edge(_v, _u);
        }
        dfs_first(1, -1, 1);
        dfs_second(1, 1);
        build(1, N, 1);
        while (Q--) {
            scanf("%s", cmd);
            if (cmd[0] == 'Q') {
                scanf("%d", &a);
                printf("%d\n", query(id[a], 1, N, 1));
            } else {
                scanf("%d %d %d", &a, &b, &c);
                if (cmd[0] == 'D') {
                    c = -c;
                }
                change(a, b, c);
            }
        }
    }
    return 0;
}

void change(int u, int v, int add)
{
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) {
            swap(u, v);
        }
        update(id[top[u]], id[u], add, 1, N, 1);
        u = father[top[u]];
    }
    if (depth[u] > depth[v]) {
        swap(u, v);
    }
    update(id[u], id[v], add, 1, N, 1);
}

int query(int tid, int low, int high, int _id)
{
    if (low == high) {
        return tree[_id];
    }
    pushdown(_id);
    int mid = (low + high) >> 1;
    if (tid <= mid) {
        return query(tid, lson);
    } else {
        return query(tid, rson);
    }
}

void update(int Left, int Right, int add, int low, int high, int _id)
{
    if (low == Left && high == Right) {
        tree[_id] += add, lazy[_id] += add;
        return;
    }
    pushdown(_id);
    int mid = (low + high) >> 1;
    if (Right <= mid) {
        update(Left, Right, add, lson);
    } else if (Left > mid) {
        update(Left, Right, add, rson);
    } else {
        update(Left, mid, add, lson);
        update(mid+1, Right, add, rson);
    }
}

void pushdown(int _id)
{
    if (lazy[_id]) {
        tree[Left(_id)] += lazy[_id], tree[Right(_id)] += lazy[_id];
        lazy[Left(_id)] += lazy[_id], lazy[Right(_id)] += lazy[_id];
        lazy[_id] = 0;
    }
}

void build(int low, int high, int _id)
{
    tree[_id] = lazy[_id] = 0;
    if (low == high) {
        tree[_id] = A[key[low]];
        return;
    }
    int mid = (low + high) >> 1;
    build(lson);
    build(rson);
}

void dfs_second(int u, int _top)
{
    top[u] = _top;
    id[u] = ++id_count;
    key[id[u]] = u;
    if (son[u] == -1) {
        return;
    }
    dfs_second(son[u], _top);
    for (int i = head[u]; ~i; i = Next[i]) {
        int v = to[i];
        if (v != son[u] && v != father[u]) {
            dfs_second(v, v);
        }
    }
}

void dfs_first(int u, int _father, int _depth)
{
    depth[u] = _depth, father[u] = _father, size[u] = 1;
    for (int i = head[u]; ~i; i = Next[i]) {
        int v = to[i];
        if (v != _father) {
            dfs_first(v, u, _depth+1);
            size[u] += size[v];
            if (son[u] == -1 || size[v] > size[son[u]]) {
                son[u] = v;
            }
        }
    }
}

void add_edge(int u, int v)
{
    to[edge] = v, Next[edge] = head[u], head[u] = edge++;
}

void Init(void)
{
    memset(head, -1, sizeof(head));
    memset(son, -1, sizeof(son));
    memset(to, -1, sizeof(to));
    edge = id_count = 0;
}

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define lson low, mid, _id<<1
#define rson mid+1, high, _id<<1|1
#define Left(_id) (_id<<1)
#define Right(_id) (_id<<1|1)

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair Pair;

const ull mod = 1e9 + 7;
const int INF = 0x7fffffff;
const int maxn = 5e4 + 10;

int N, M, Q, id_count, _u, _v, a, b, c;
int A[maxn], size[maxn], son[maxn], father[maxn], depth[maxn], id[maxn], key[maxn], top[maxn];
int head[maxn], to[2*maxn], Next[2*maxn], edge;
int C[maxn];
char cmd[5];

void Init(void);
void add_edge(int u, int v);
void dfs_first(int u, int _father, int _depth);
void dfs_second(int u, int _top);
int query(int x);
inline int lowbit(int x);
void update(int x, int add);
void change(int u, int v, int add);

int main()
{
#ifdef __AiR_H
    freopen("in.txt", "r", stdin);
#endif // __AiR_H
    while (scanf("%d %d %d", &N, &M, &Q) != EOF) {
        Init();
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &A[i]);
        }
        for (int i = 1; i <= M; ++i) {
            scanf("%d %d", &_u, &_v);
            add_edge(_u, _v), add_edge(_v, _u);
        }
        dfs_first(1, -1, 1);
        dfs_second(1, 1);
        memset(C, 0, sizeof(C));
        for (int i = 1; i <= N; ++i) {
            update(id[i], A[i]), update(id[i]+1, -A[i]);
        }
        while (Q--) {
            scanf("%s", cmd);
            if (cmd[0] == 'Q') {
                scanf("%d", &a);
                printf("%d\n", query(id[a]));
            } else {
                scanf("%d %d %d", &a, &b, &c);
                if (cmd[0] == 'D') {
                    c = -c;
                }
                change(a, b, c);
            }
        }
    }
    return 0;
}

void change(int u, int v, int add)
{
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) {
            swap(u, v);
        }
        update(id[top[u]], add), update(id[u]+1, -add);
        u = father[top[u]];
    }
    if (depth[u] > depth[v]) {
        swap(u, v);
    }
    update(id[u], add), update(id[v]+1, -add);
}

int query(int x)
{
    int ret = 0;
    while (x > 0) {
        ret += C[x], x -= lowbit(x);
    }
    return ret;
}

void update(int x, int add)
{
    while (x <= maxn) {
        C[x] += add, x += lowbit(x);
    }
}

inline int lowbit(int x)
{
    return (x & (-x));
}

void dfs_second(int u, int _top)
{
    top[u] = _top;
    id[u] = ++id_count;
    key[id[u]] = u;
    if (son[u] == -1) {
        return;
    }
    dfs_second(son[u], _top);
    for (int i = head[u]; ~i; i = Next[i]) {
        int v = to[i];
        if (v != son[u] && v != father[u]) {
            dfs_second(v, v);
        }
    }
}

void dfs_first(int u, int _father, int _depth)
{
    depth[u] = _depth, father[u] = _father, size[u] = 1;
    for (int i = head[u]; ~i; i = Next[i]) {
        int v = to[i];
        if (v != _father) {
            dfs_first(v, u, _depth+1);
            size[u] += size[v];
            if (son[u] == -1 || size[v] > size[son[u]]) {
                son[u] = v;
            }
        }
    }
}

void add_edge(int u, int v)
{
    to[edge] = v, Next[edge] = head[u], head[u] = edge++;
}

void Init(void)
{
    memset(head, -1, sizeof(head));
    memset(son, -1, sizeof(son));
    memset(to, -1, sizeof(to));
    edge = id_count = 0;
}

点击复制链接与好友分享!回本站首页