【数据结构】树链剖分

引言

我在之前写过的一片关于树状数组的文章中有一道题，是利用dfs的方法将一棵树“拍扁”，称为一维数组，并将树中的查询和修改转换成一维数组中的查询与修改。

之所以可以使用dfs这种简单的方法是因为题目中的查询是针对子树的查询，dfs序列可以很好的应用。

但是如果查询是针对树中一条路径的话，那么dfs这种简单的序列就不能使用了。

面对这种问题，我们的解决方法是：树链剖分。

树链剖分

核心思想

树链剖分实际上是将树划分成很多的链，并将这些链合在一起，用线段树维护。所以，自然支持区间操作和单点操作。

所以，关键其实是树的划分方法。

划分的核心思想是轻重链划分，这种划分方法有一个非常好的性质：从根到某一点的路径上，不超过logn条轻边，且不超过logn条重路径。

而这就是树链剖分(logn)^2时间复杂度的保证。

具体的讲解可以参考：http://blog.csdn.net/vecsun/article/details/48938777

对英语不发憷的同学可以看看这篇外国人写的：https://blog.anudeep2011.com/heavy-light-decomposition/

说实话，总感觉外国人的东西，无论是课本还是博客，思维过程都特别清楚。

而包括我自己在内的中国人，写东西总是一步到位。

当然，题外话，我写这些博客主要是为了我长时间不接触算法之后能快速回忆起算法的核心思想，而不是去告诉一个刚学算法的人怎么完全掌握这个算法。

模板

树链剖分主要有两种情况，一种是维护边权的，一种是维护点权的。

中间存在一些细微的差别，但是核心思想是相同的。

模板例行见应用～

应用

大名鼎鼎的SPOJ QTREE系列前两道是模板题，可以做一下，后面的QTREE我就不知道了。

因为懒得取SPOJ的网站，所以就取HDU找了一个模板题：HDU 3966。

维护点权的～

有一点要注意，树链剖分使用dfs遍历经常会爆栈，所以我推荐使用我这样的bfs的写法～

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

#define N 50100
#define M 100010

int n, m, p;
int cnt, tot;
int head[N], nxt[M], to[M];
int det[N << 2];
int ind[N];
int fa[N], top[N], dep[N], sz[N], son[N];
int q[N];
int a[N];

void add(int u, int v) {
    to[cnt] = v; nxt[cnt] = head[u]; head[u] = cnt++;
}

void init() {
    memset(son, 0, sizeof son);
    memset(head, -1, sizeof head);
    tot = cnt = 0;
}

void preprocess() {
    // 获取fa, dep
    int h = 1, t = 2, sta;
    q[1] = 1;
    dep[1] = 1;
    fa[1] = 0;
    while (h < t) {
        sta = q[h++];
        sz[sta] = 1;
        for (int i = head[sta]; ~i; i = nxt[i]) {
            if (fa[sta] != to[i]) {
                fa[to[i]] = sta;
                dep[to[i]] = dep[sta] + 1;
                q[t++] = to[i];
            }
        }
    }
    // 使用bfs队列模拟dfs，避免爆栈
    // 计算sz， son
    for (int j = t - 1; j >= 1; j--) {
        sta = q[j];
        for (int i = head[sta]; ~i; i = nxt[i]) {
            if (fa[sta] != to[i]) {
                sz[sta] += sz[to[i]];
                if (sz[to[i]] > sz[son[sta]])
                    son[sta] = to[i];// sz[0] == 0
            }
        }
    }
    // 计算top
    top[1] = 1;
    for (int i = 2; i < t; i++) {
        sta = q[i];
        if (sta == son[fa[sta]]) top[sta] = top[fa[sta]];
        else top[sta] = sta;
    }
    // 将树拍扁，求ind
    for (int j = 1; j <= n; j++) {
        if (top[j] == j) {
            for (int i = j; i; i = son[i])
                ind[i] = ++tot;
        }
    }
}

void pushdown(int u) {
    det[u << 1] += det[u];
    det[u << 1 | 1] += det[u];
    det[u] = 0;
}

void build(int u, int L, int R) {
    det[u] = 0;
    if (L == R) return;
    int MID = (L + R) >> 1;
    build(u << 1, L, MID);
    build(u << 1 | 1, MID + 1, R);
}

int query(int u, int L, int R, int p) {
    if (L == R) return det[u];
    if (det[u] != 0) pushdown(u);
    int MID = (L + R) >> 1;
    if (p <= MID) return query(u << 1, L, MID, p);
    return query(u << 1 | 1, MID + 1, R, p);
}

void update(int u, int L, int R, int l, int r, int k) {
    if (l <= L && r >= R) {
        det[u] += k;
        return;
    }
    int MID = (L + R) >> 1;
    if (l <= MID) update(u << 1, L, MID, l, r, k);
    if (r > MID) update(u << 1 | 1, MID + 1, R, l, r, k);
}

void update_range(int x, int y, int k) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        update(1, 1, tot, ind[top[x]], ind[x], k);
        x = fa[top[x]];
    }
    if (ind[x] > ind[y]) swap(x, y);// 在一条重链上
    update(1, 1, tot, ind[x], ind[y], k);
}

int main() {
    while (scanf("%d%d%d", &n, &m, &p) != EOF) {
        int x, y, z;
        char qu[3];
        init();
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", &x, &y);
            add(x, y);
            add(y, x);
        }
        preprocess();
        build(1, 1, tot);
        while (p--) {
            scanf("%s", qu);
            if (qu[0] == 'Q') {
                scanf("%d", &x);
                // 单点查询
                printf("%d\n", a[x] + query(1, 1, tot, ind[x]));
            }
            else {
                scanf("%d%d%d", &x, &y, &z);
                // 区间更新
                if (qu[0] == 'D') update_range(x, y, -z);
                else update_range(x, y, z);
            }
        }
    }
    return 0;
}

（待更新…）