树链剖分—重链剖分小记

发布于 2019-10-04  607 次阅读

树链剖分可以将一棵树剖为很多条链，这样据可以供其他的数据结构维护，（树剖/链剖）有多种形式，如 重链剖分 ， 长链剖分 和用于 Link/cut Tree 的剖分（有时被称作“实链剖分”），大多数情况下（没有特别说明时），“树链剖分”都指“重链剖分”，本文所讲的也是“重链剖分”。

树链剖分是做什么的

为了便于理解，我从oi-wiki上引用些图文来解释（个人感觉解释的比较直观）：

定义 重子节点 表示其子节点中子树最大的子结点。如果有相同的，任意取。如果没有子节点，就没有。

定义 轻子节点 表示剩余的子结点。

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

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

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

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

看一张图就明白了

它可以用于求LCA(据说比倍增的LCA快)，它还可以将一棵树拆成很多条链，方便线段树维护等。

实现

树链剖分代码不长，但是他要定义许多变量，emmmmmm，比较烦人，树链剖分的初始化就两个bfs。

存储

struct node
{
    int to, next;
} edge[maxn];

数组定义

int fa[i]; //i节点的父亲
int son[i]; //i节点的重儿子
int dep[i]; //i节点的深度
int size[i]; //以i为根的子树结点个数

int id[i]; //i节点在dfs树中的dfs序
int top[i]; //i节点所在链的顶端节点的编号
int rnk[i]; //i节点剖分以后的新结点编号

初始化

重链剖分需要在两个dfs中预处理出这些数组

第一个bfs求的是 fa,son,d,size。

代码如下（还是很好理解的）：

void dfs1(int u, int f, int deep)
{
    fa[u] = f;
    dep[u] = deep;
    size[u] = 1;
    for (int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == f)
            continue;
        dfs1(v, u, deep + 1);
        size[u] += size[v];         //回溯
        if (size[v] > size[son[u]]) //贪心选择
            son[u] = v;
    }
}

dfs跑完大概是这样的，大家可以手动模拟一下

第一个bfs求的则是剩下的

void dfs2(int u, int t)
{
    top[u] = t;
    id[u] = ++cnt;
    rnk[cnt] = u; //序号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 != f[u])
            dfs2(v, v);
    }
}

例子：求LCA

让两个点不断向上跳到自己的链的顶端。一旦他们跳到了同一个链上，两个点中深度较小的点即为LCA。

上代码：

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

Luogu P3379 【模板】最近公共祖先（LCA） 代码：

#include <iostream>
#include <algorithm>
using namespace std;

int fa[500005];   //i节点的父亲
int son[500005];  //i节点的重儿子
int dep[500005];  //i节点的深度
int size[500005]; //以i为根的子树结点个数
int top[500005];  //i节点所在链的顶端节点的编号

int cnt = 0;

struct node
{
    int to, next;
} edge[1000005];

int head[500005], num = 0;

void add_edge(int from, int to)
{
    num++;
    edge[num].next = head[from];
    head[from] = num;
    edge[num].to = to;
}

void dfs1(int u, int f, int deep)
{
    fa[u] = f;
    dep[u] = deep;
    size[u] = 1;
    for (int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == f)
            continue;
        dfs1(v, u, deep + 1);
        size[u] += size[v];         //回溯
        if (size[v] > size[son[u]]) //贪心选择
            son[u] = v;
    }
}

void dfs2(int u, int t)
{
    top[u] = t;
    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])
            dfs2(v, v);
    }
}

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

int n, m, s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        add_edge(x, y);
        add_edge(y, x);
    }
    dfs1(s, s, 1);
    dfs2(s, s);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
    return 0;
}

树上路径维护，子树维护

直接上题 P3384 【模板】重链剖分/树链剖分

已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

  • 1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。

  • 2 x y，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。

  • 3 x z，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。

  • 4 x 表示求以 $x$ 为根节点的子树内所有节点值之和

【数据规模】

对于 $30\%$ 的数据： $1 \leq N \leq 10$，$1 \leq M \leq 10$；

对于 $70\%$ 的数据： $1 \leq N \leq {10}^3$，$1 \leq M \leq {10}^3$；

对于 $100\%$ 的数据： $1\le N \leq {10}^5$，$1\le M \leq {10}^5$，$1\le R\le N$，$1\le P \le 2^{31}-1$。

树链剖分后，我们就可以将树上的路径问题转化为链上的路径问题，从而使用线段树等数据结构进行维护。

在树链剖分的过程中，我们需要维护每个节点的父节点、子节点、重儿子、深度等信息。这些信息可以通过两次 DFS 遍历树来计算得到。第一次 DFS 用于计算每个节点的子树大小和重儿子，第二次 DFS 用于计算每个节点的父节点、深度等信息。

树链剖分的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。它可以用于解决树上路径问题，如树上点的修改、区间查询等问题。

首先先用树剖的两个dfs把重链剖分出来，

接着，我们需要实现树链剖分后的路径查询和修改操作：

// 路径查询
long long tree_sum(int x, int y) {
    long ans = 0;
    while (top[x] != top[y]) { // 类似树剖lca的思想
        if (dep[top[x]] < dep[top[y]]) // 保证x在更深的重链上
            swap(x, y);
        ans = (ans % p + sum(1, n, 1, id[top[x]], id[x]) % p) % p; // 将x所在重链的和加入答案
        x = fa[top[x]]; // 跳到x所在重链的上一条重链
    }
    if (dep[y] < dep[x]) // 保证x在更深的位置
        swap(x, y);
    ans = (ans % p + sum(1, n, 1, id[x], id[y]) % p) % p; // 将x到y路径上的和加入答案
    return ans;
}

// 路径修改
void tree_add(int x, int y, long w) {
    while (top[x] != top[y]) { // 类似树剖lca的思想
        if (dep[top[x]] < dep[top[y]]) // 保证x在更深的重链上
            swap(x, y);
        modify(1, n, 1, id[top[x]], id[x], w); // 修改x所在重链上的节点
        x = fa[top[x]]; // 跳到x所在重链的上一条重链
    }
    if (dep[x] > dep[y]) // 保证x在更深的位置
        swap(x, y);
    modify(1, n, 1, id[x], id[y], w); // 修改x到y路径上的节点
}

// 子树修改
modify(1, n, 1, id[x], id[x] + siz[x] - 1, y);
// 子树查询
sum(1, n, 1, id[x], id[x] + siz[x] - 1);

建立线段树的时候要dfs序的节点（也就是新节点对应到真实树上的节点），其他的操作其实就是普通的线段树。

void build(int l, int r, int rt)
{
    if (l == r)
    {
        z[rt] = rnk[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    update(rt);
}