[Note] 树链剖分

[L4] 树链剖分

1. 生态位

• 识别:

  1. 树上路径修改/查询: “将 $u$ 到 $v$ 路径上所有点权值 $+k$”、“查询 $u$ 到 $v$ 路径权值和”。

  2. 子树修改/查询: “将以 $u$ 为根的子树内所有点权值 $+k$”。

  3. 结合律信息: 维护的信息满足结合律（和、最大值），本质是线段树能维护的信息。

• 地位：树论与数据结构之间的桥。它将非线性的树结构转化为线性的数组结构。

• 用途：将树上路径操作复杂度从 $O(N)$ 降维至 $O(\log^2 N)$，子树操作降维至 $O(\log N)$。同时提供常数极小的 LCA 查询。

2. 逻辑支点

2.1 核心原理：轻重边划分

为了让树变得“像数组一样连续”，我们根据 子树大小 (size) 对边进行分类：

• 重儿子: 父节点的所有儿子中，子树节点数 (sz) 最多的那个。

• 轻儿子: 除重儿子外的其他儿子。

• 重链: 由重边首尾相连形成的路径。

2.2 物理性质

1. DFN 序连续性:

   • 在 DFS 过程中优先遍历重儿子。

   • 推论 1: 每一条重链上的节点的 DFN 序是连续的（对应线段树上的一段区间）。

   • 推论 2: 任意一颗子树内的 DFN 序也是连续的。

2. 复杂度保证:

   • 从树上任意一点走到根节点，经过的轻边数量不超过 $O(\log N)$ 条，经过的重链数量也不超过 $O(\log N)$ 条。

   • 因此，路径修改/查询相当于在线段树上操作 $O(\log N)$ 个区间。

3. 实战部署

▶

树链剖分模版

const int maxn = 1e5 + 50;

// 1. 树的基础结构
vector<int> adj[maxn];
int fa[maxn], dep[maxn], sz[maxn], son[maxn];    // son: 重儿子
int top[maxn], dfn[maxn], rnk[maxn], timer;      // top: 链顶, dfn: DFS序, rnk: DFS序对应的节点
int w[maxn];        // 节点的初始权值
int n, m, r, mod;   // mod 用于取模题目

// 2. 线段树部分 (Segment Tree)
struct Node {
    int l, r;
    ll sum, add;
} tr[maxn << 2];

#define ls u << 1
#define rs u << 1 | 1

void pushup( int u ) {
    tr[u].sum = ( tr[ls].sum + tr[rs].sum ) % mod;
}

void pushdown( int u ) 
{
    if( !tr[u].add ) return;
    ll t = tr[u].add;
    tr[ls].sum = ( tr[ls].sum + t * ( tr[ls].r - tr[ls].l + 1 ) ) % mod;
    tr[rs].sum = ( tr[rs].sum + t * ( tr[rs].r - tr[rs].l + 1 ) ) % mod;
    tr[ls].add = ( tr[ls].add + t ) % mod;
    tr[rs].add = ( tr[rs].add + t ) % mod;
    tr[u].add = 0;
}

void build( int u, int l, int r ) 
{
    tr[u] = { l, r, 0, 0 };
    if( l == r ) 
    {
        tr[u].sum = w[rnk[l]] % mod; // 注意这里用 rnk[l] 获取原节点编号
        return;
    }
    int mid = l + r >> 1;
    build( ls, l, mid );
    build( rs, mid + 1, r );
    pushup( u );
}

void modify( int u, int l, int r, ll val ) 
{
    if( l <= tr[u].l && tr[u].r <= r ) 
    {
        tr[u].sum = ( tr[u].sum + val * ( tr[u].r - tr[u].l + 1 ) ) % mod;
        tr[u].add = ( tr[u].add + val ) % mod;
        return;
    }
    pushdown( u );
    int mid = tr[u].l + tr[u].r >> 1;
    if( l <= mid ) modify( ls, l, r, val );
    if( r > mid ) modify( rs, l, r, val );
    pushup( u );
}

ll query( int u, int l, int r ) 
{
    if( l <= tr[u].l && tr[u].r <= r ) return tr[u].sum;
    pushdown( u );
    int mid = tr[u].l + tr[u].r >> 1;
    ll res = 0;
    if( l <= mid ) res = ( res + query( ls, l, r ) ) % mod;
    if( r > mid ) res = ( res + query( rs, l, r ) ) % mod;
    return res;
}

// 3. 树链剖分核心函数
// DFS 1: 计算 size, depth, father, heavy son
void dfs1( int u, int p ) 
{
    dep[u] = dep[p] + 1; fa[u] = p; sz[u] = 1;
    for( int v : adj[u] ) 
    {
        if( v == p ) continue;
        dfs1( v, u );
        sz[u] += sz[v];
        if( sz[v] > sz[son[u]] ) son[u] = v;
    }
}

// DFS 2: 建立重链, 记录 dfn, top
void dfs2( int u, int t ) 
{
    top[u] = t; dfn[u] = ++timer; rnk[tim] = u;
    if( !son[u] ) return;   // 叶子节点
    dfs2( son[u], t );      // 优先遍历重儿子，保持重链 dfn 连续
    for( int v : adj[u] ) 
    {                       // 轻儿子的 top 是它自己
        if( v == fa[u] || v == son[u] ) continue;
        dfs2( v, v );     
    }
}

// 4. 树上操作接口
// 路径修改
void modify_path( int u, int v, int val ) 
{
    while( top[u] != top[v] ) 
    {
        if( dep[top[u]] < dep[top[v]] ) swap( u, v );
        modify( 1, dfn[top[u]], dfn[u], val ); // 修改 u 到 top[u]
        u = fa[top[u]];
    }
    if( dep[u] > dep[v] ) swap( u, v );
    modify( 1, dfn[u], dfn[v], val ); // 同一条链上
}

// 路径查询
ll query_path( int u, int v ) 
{
    ll res = 0;
    while( top[u] != top[v] ) 
    {
        if( dep[top[u]] < dep[top[v]] ) swap( u, v );
        res = ( res + query( 1, dfn[top[u]], dfn[u] ) ) % mod;
        u = fa[top[u]];
    }
    if( dep[u] > dep[v] ) swap( u, v );
    res = ( res + query( 1, dfn[u], dfn[v] ) ) % mod;
    return res;
}

// 子树操作：利用子树 DFN 连续性
void modify_subtree( int u, int val )
{
    modify( 1, dfn[u], dfn[u] + sz[u] - 1, val );
}

ll query_subtree( int u )
{
    return query( 1, dfn[u], dfn[u] + sz[u] - 1 );
}

4. 知识关联

• 母题：[[Leaf] [P3384] 重链剖分] —— 包含路径修/查、子树修/查的完整功能演示。

• 关联笔记:

  • 线段树基础理论：HLD 的处理工具。

  • LCA 体系：HLD 也是一种极速求 LCA 的方式（ query_path 过程中最后停留的浅点即为 LCA ）。

  • [[DSU on Tree]]：同样利用轻重边性质，但解决的是不带修改的子树统计问题。