树链剖分（重链剖分）
Eva.Q Lv9
2022-08-02 13:32:31

“我发现了比蛋糕更好的东西。”

“不，你没有。” 男孩说。

“我有。” 鼹鼠说。

“是什么？”

“拥抱。它比蛋糕更持久。”

树链剖分的思想

树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。

具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

重链剖分

相关定义

重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。

轻子节点 表示剩余的所有子结点。

从这个结点到重子节点的边为 重边。

到其他轻子节点的边为 轻边。

若干条首尾衔接的重边构成 重链。

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

代码

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
int fa[N], dep[N], son[N], sz[N], top[N], dfn[N], cnt;

void dfs1(int u, int d) {
    dep[u] = d;
    sz[u] = 1;
    int mxid = 0;
    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!fa[v]) {
            fa[v] = u; dfs1(v, d + 1); sz[u] += sz[v];
            if (sz[v] > sz[mxid]) mxid = v;
        }
    }
    son[u] = mxid;
}

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++cnt;
    if (son[u]) dfs2(son[u], t);
    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) dfs2(v, v);
    }
}

应用

重链剖分 可以将树上的任意一条路径划分成不超过 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。

重链剖分还能保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。

如：

  1. 修改 树上两点之间的路径上 所有点的值。
  2. 查询 树上两点之间的路径上 节点权值的 和/极值/其它（在序列上可以用数据结构维护，便于合并的信息）。

除了配合数据结构来维护树上路径信息，树剖还可以用来 （且常数较小）地求 LCA。

求 LCA

考虑以下两种情况：

  1. , 在一条重链上，那深度浅的那一个就是他们的 LCA
  2. , 不在一条重链上，比较 dep[top[u]] 和 dep[top[v]] ，深度较浅的跳到其父亲，如此循环，最终会回到第 1 种情况。
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 500007
#define M 1000007

struct node {int to, nxt;} e[M];
int hd[N], tot;

inline void add(int u, int v) {
    e[++tot].to = v; e[tot].nxt = hd[u]; hd[u] = tot;
    e[++tot].to = u; e[tot].nxt = hd[v]; hd[v] = tot;
}

int fa[N], dep[N], son[N], sz[N], top[N], dfn[N], cnt;

void dfs1(int u, int d) {
    dep[u] = d;
    sz[u] = 1;
    int mxid = 0;
    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!fa[v]) {
            fa[v] = u; dfs1(v, d + 1); sz[u] += sz[v];
            if (sz[v] > sz[mxid]) mxid = v;
        }
    }
    son[u] = mxid;
}

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++cnt;
    if (son[u]) dfs2(son[u], t);
    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) dfs2(v, v);
    }
}

inline int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]])
            u = fa[top[u]];
        else 
            v = fa[top[v]];
    }
    return dep[u] > dep[v] ? v : u;
}

int main() {
    int n = rd(), m = rd(), s = rd();
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd(); add(u, v);
    }
    fa[s] = s;
    dfs1(s, 1); dfs2(s, s);
    for (int i = 1; i <= m; ++i) {
        int a = rd(), b = rd();
        printf("%d\n", lca(a, b));
    }
    return 0;
}

子树加、查询 & 路径加、查询

洛谷 P3384

在 dfs 序中，子树是连续的一段，而一段路径至多分为 段。配合线段树解决这一问题。

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
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 100007

struct no {int to, nxt;} e[N << 1];
int hd[N], tot;

inline void add(int u, int v) {
    e[++tot].to = v; e[tot].nxt = hd[u]; hd[u] = tot;
    e[++tot].to = u; e[tot].nxt = hd[v]; hd[v] = tot;
}

int fa[N], dep[N], son[N], sz[N], top[N], dfn[N], cnt, ran[N];

void dfs1(int u, int d) {
    dep[u] = d;
    sz[u] = 1;
    int mxid = 0;
    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!fa[v]) {
            fa[v] = u; dfs1(v, d + 1); sz[u] += sz[v];
            if (sz[v] > sz[mxid]) mxid = v;
        }
    }
    son[u] = mxid;
}

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++cnt;
    ran[cnt] = u;
    if (son[u]) dfs2(son[u], t);
    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) dfs2(v, v);
    }
}

struct node{
  int ls, rs;
  ll lazy, sum;
}c[N << 1];

int totnode, rot, a[N], p;

inline int newn(){
    return ++totnode;
}

inline void pushup(int rt) {
    c[rt].sum = (c[c[rt].ls].sum + c[c[rt].rs].sum) % p;
}

void build(int &rt, int l, int r){
    if (rt == 0) rt = newn();
    if (l == r) {c[rt].sum = a[ran[l]]; return;}
    int mid = (l + r) >> 1;
    build(c[rt].ls, l, mid);
    build(c[rt].rs, mid + 1, r);
    pushup(rt);
}

void pushdown(int rt, int ln, int rn) {//ln 左二子区间长度 rn 右儿子区间长度
    if (c[rt].lazy) {
        c[c[rt].ls].lazy = (c[c[rt].ls].lazy + c[rt].lazy) % p;
        c[c[rt].rs].lazy = (c[c[rt].rs].lazy + c[rt].lazy) % p;
        c[c[rt].ls].sum = (c[c[rt].ls].sum + c[rt].lazy * ln % p) % p;
        c[c[rt].rs].sum = (c[c[rt].rs].sum + c[rt].lazy * rn % p) % p;
        
        c[rt].lazy = 0;
    }
}

void update(int rt, int l, int r, int L, int R, int val) {
    if (L <= l && r <= R) {
        c[rt].sum = (c[rt].sum + val * (r - l + 1)) % p;
        c[rt].lazy = (c[rt].lazy  + val) % p;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    if (L <= mid) update(c[rt].ls, l, mid, L, R, val);
    if (R > mid) update(c[rt].rs, mid + 1, r, L, R, val);
    pushup(rt);
}

inline ll query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return c[rt].sum;
    ll ans = 0;
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    if (L <= mid) ans = (ans + query(c[rt].ls, l, mid, L, R)) % p;
    if (R > mid) ans = (ans + query(c[rt].rs, mid + 1, r, L, R)) % p;
    return ans;
}

int main() {
    int n = rd(), m = rd(), s = rd(); p = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd() % p;
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd(); add(u, v);
    }
    fa[s] = s;
    dfs1(s, 1); dfs2(s, s); build(rot, 1, n);
    for (int i = 1; i <= m; ++i) {
        int op = rd();
        if (op == 1) { // 路径加
            int x = rd(), y = rd(), val = rd();
            while (top[x] != top[y]) {
                if (dep[top[x]] > dep[top[y]]) {
                    update(rot, 1, n, dfn[top[x]], dfn[x], val);
                    x = fa[top[x]];
                }
                else {
                    update(rot, 1, n, dfn[top[y]], dfn[y], val);
                    y = fa[top[y]];
                }
            }
            if (dep[x] > dep[y]) swap(x, y);
            update(rot, 1, n, dfn[x], dfn[y], val);
        } else if (op == 2) { // 路径查询
            int x = rd(), y = rd();
            int ans = 0;
            while (top[x] != top[y]) {
                if (dep[top[x]] > dep[top[y]]) {
                    ans = (ans + query(rot, 1, n, dfn[top[x]], dfn[x])) % p;
                    x = fa[top[x]];
                }
                else {
                    ans = (ans + query(rot, 1, n, dfn[top[y]], dfn[y])) % p;
                    y = fa[top[y]];
                }
            }
            if (dep[x] > dep[y]) swap(x, y);
            ans = (ans + query(rot, 1, n, dfn[x], dfn[y])) % p;
            printf("%d\n", ans);
        } else if (op == 3) { // 子树加
            int x = rd(), val = rd();
            update(rot, 1, n, dfn[x], dfn[x] + sz[x] - 1, val);
        } else { // 子树查询
            int x = rd();
            printf("%lld\n", query(rot, 1, n, dfn[x], dfn[x] + sz[x] - 1));
        }
    }
    return 0;
}
  • Post title：树链剖分（重链剖分）
  • Post author：Eva.Q
  • Create time：2022-08-02 13:32:31
  • Post link：https://qyy/2022/08/02/Algorithm/heavy path decomposition/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.