笔记汇总

树链剖分是一种将 树上路径 转化成 线性路径，并用 线段树 做区间运算的算法。

一棵树所蕴含信息大于同长线段蕴含的信息，如果要将线段树压至线段上，就需要将树划分。

划分必定与树的倾向有关。

性质

通过构造，树里的任意一条路径都可以转化成 $O(logn)$ 段连续区间。

所以树上点的编号要尽量的连续，如此，需要先对结点进行划分，如，

子树节点少的的代表是轻儿子，多的的代表是重儿子。

因为在同点下层子节点中只有一个重儿子，如果想要连续，顺着重儿子很有价值（因为一顺到底）

但树上存在很多的轻儿子，为了让两儿子融洽，故而创立了重链（轻头重身），

对于任意的一条路径，其起点和终点有，祖孙关系，同祖关系。

若是祖孙关系，则它们在一条链上，因为任意点要么是头要么是身，

易知，所有非叶子结点都在一条长大于一的路径中，

而另一点的最劣解，为全走轻点，而最佳构造是完全二叉树，其点至多为 $logn$，即树的深度。

若是同祖关系，则最大可为 $2logn$，因为这是最佳构造，所以也是最大的划分。

我们对结点按照重儿子优先来先序遍历，并赋予线性空间的编号（子树内编号连续）

因为区间操作需要知道涉及的区间，我们仿照并查集建立代表元。

实现

找到所有应修改（查询）的区间（$O(logn)$），用线段树修改（查询）($O(log^2n)$)

找应修改区间的操作类似 $LCA$，但不需要倍增数组（逐一由代表元往上升）

这需要我们维护深度（类似 $LCA$）、代表元及其父亲（用来上升）。

我们每次都走深度较低的指针，线段树在线修改/查询（方便判边界）。

最后的重链要退出后再加，免得加两次。

步骤一

预处理所有节点的 重儿子 以及子树内 节点的数量 和 每个节点的 父节点

//dfs1预处理
void dfs1(int u, int father, int depth)
{
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);  // 先要知道子树大小才能知道谁是重儿子
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j; // 重儿子son是子树节点最多的儿子
    }
}

步骤二

树链剖分，找出每个节点所属 重链 的 顶点，dfs序的编号，并建立 u 到 id 的 w 映射

//dfs2做剖分（t是重链的顶点）
void dfs2(int u, int t)
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t; 
    // 编号; 被编号点的线性空间映射; 代表元;
    if (!son[u]) return; //叶节点结束
    dfs2(son[u], t); //重儿子重链剖分
    //处理轻儿子
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j); //轻儿子的重链顶点就是他自己
    }
}

维护树上两个点的路径

void update_path(int u, int v, int k)   // u->v的路径上所有节点权值加k
{
    while (top[u] != top[v])    //向上爬找到相同重链；同时维护所有经过的重链
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);  // 全部由下往上利于辨认边界
        update(1, id[top[u]], id[u], k);    //dfs序原因，上面节点的id必然小于下面节点的id
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    update(1, id[v], id[u], k); //在同一重链中，处理剩余区间
}

拓展

因为子树内编号连续，维护子树大小就可以区间修改这一部分了。

维护以一个节点为根节点的子树

void update_tree(int u, int k) //子树全部加上k
{
    update(1, id[u], id[u] + sz[u] - 1, k); //由于dfs序的原因，可以利用子树节点个数直接找到区间
}

拓展用途

可以维护区间满足及不满足信息量（信息总量 $-$ 满足信息量）

id[u] - id[top[x]] + 1 // 单条重链上的信息总量