高效树上路径操作与子树维护的重链剖分与线段树结合

核心逻辑与数学原理

本章将树的重链剖分与线段树（Segment Tree）进行强耦合，解决工业级、高并发的树上复杂路径修改、子树维护与复合逻辑检索难题。其核心数学支撑在于拓扑映射的区间重叠性与独立性。

通过重链剖分，树上的两个关键空间域被完美同构到线段树的线性叶子节点区间 $[1, N]$ 中：

1. 路径域映射：任意路径 $(u, v)$ 被切分为至多 $O( ext{log} N)$ 段连续的剖分序区间。每段区间在线段树中对应一个或多个节点，利用线段树的区间标记下传（Lazy Tag）可将路径修改与查询的时间复杂度严格压制在 $O( ext{log}^2 N)$。
2. 子树域映射：以 $u$ 为根的子树，在剖分序中对应一段严格连续的闭区间 $[ ext{dfn}[u], ext{dfn}[u] + ext{siz}[u] - 1]$。对子树的整体修改与查询，在线段树中只需进行一次区间操作，时间复杂度为 $O( ext{log} N)$。

算法推导与状态设计

设计一套完整的树剖线段树复合系统，需要对两套状态进行映射维护。

1. 线段树状态设计

对于拍平后的序列 $ ext{rnki}[i]$（表示新序列第 $i$ 个位置对应的原树节点编号），线段树节点结构体定义为：

struct Node {
    int l, r;
    long long sum;
    long long lazy;
} tree[MAXN << 2];

• 状态转移方程（PushUp）：

$$ ext{tree}[p]. ext{sum} = ext{tree}[p imes 2]. ext{sum} + ext{tree}[p imes 2 + 1]. ext{sum}$$

• 标记下传方程（PushDown）： 若 $ ext{tree}[p]. ext{lazy} eq 0$，对于左右子节点 $lc = p imes 2, rc = p imes 2 + 1$：

$$ ext{tree}[lc]. ext{lazy} ext{ }\leftarrow ext{tree}[lc]. ext{lazy} + ext{tree}[p]. ext{lazy}$$

$$ ext{tree}[lc]. ext{sum} ext{ }\leftarrow ext{tree}[lc]. ext{sum} + ext{tree}[p]. ext{lazy} imes ( ext{tree}[lc].r - ext{tree}[lc].l + 1)$$

右子节点同理，下传后 $ ext{tree}[p]. ext{lazy} = 0$。

2. 树上路径修改与查询推导

对于查询/修改路径 $(u, v)$：

1. 比较两点链顶的拓扑深度 $ ext{dep}[ ext{top}[u]]$ 与 $ ext{dep}[ ext{top}[v]]$。
2. 不妨设 $ ext{dep}[ ext{top}[u]] ext{ }\ge ext{ }\text{dep}[ ext{top}[v]]$，此时 $u$ 所在的重链整体更深。在线段树中对区间 $[ ext{dfn}[ ext{top}[u]], ext{dfn}[u]]$ 进行操作。
3. 令 $u = ext{fa}[ ext{top}[u]]$，跳出当前重链，进入上一层拓扑结构。
4. 重复步骤 1-3，直到 $ ext{top}[u] == ext{top}[v]$。
5. 此时两点处于同一条重链，最后对线段树区间 $[ ext{min}( ext{dfn}[u], ext{dfn}[v]), ext{max}( ext{dfn}[u], ext{dfn}[v])]$ 进行一次收尾操作。

C++ 标准源码

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 100005;

// 树形拓扑结构
std::vector<int> adj[MAXN];
int w_init[MAXN]; // 原树节点的初始权值
int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN];
int top[MAXN], dfn[MAXN], rnki[MAXN], tim;

// 线段树核心结构
struct SegTree {
    int l, r;
    long long sum;
    long long lazy;
} tree[MAXN << 2];

// 树剖第一遍 DFS
void dfs1(int u, int p) {
    fa[u] = p;
    dep[u] = dep[p] + 1;
    siz[u] = 1;
    son[u] = 0;
    int max_siz = 0;
    for (size_t i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (v == p) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > max_siz) {
            max_siz = siz[v];
            son[u] = v;
        }
    }
}

// 树剖第二遍 DFS
void dfs2(int u, int t) {
    top[u] = t;
    tim++;
    dfn[u] = tim;
    rnki[tim] = u;
    if (!son[u]) return;
    dfs2(son[u], t); // 优先重儿子
    for (size_t i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

// 线段树基础驱动函数
inline void push_up(int p) {
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}

inline void push_down(int p) {
    if (tree[p].lazy) {
        int lc = p << 1, rc = p << 1 | 1;
        long long lazy_val = tree[p].lazy;

        tree[lc].lazy += lazy_val;
        tree[lc].sum += lazy_val * (tree[lc].r - tree[lc].l + 1);

        tree[rc].lazy += lazy_val;
        tree[rc].sum += lazy_val * (tree[rc].r - tree[rc].l + 1);

        tree[p].lazy = 0;
    }
}

void build(int p, int l, int r) {
    tree[p].l = l;
    tree[p].r = r;
    tree[p].lazy = 0;
    if (l == r) {
        tree[p].sum = w_init[rnki[l]]; // 致命踩坑点：必须使用新序列索引映射回原树节点的权值
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    push_up(p);
}

void update_range(int p, int l, int r, long long val) {
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].sum += val * (tree[p].r - tree[p].l + 1);
        tree[p].lazy += val;
        return;
    }
    push_down(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) update_range(p << 1, l, r, val);
    if (r > mid) update_range(p << 1 | 1, l, r, val);
    push_up(p);
}

long long query_range(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) {
        return tree[p].sum;
    }
    push_down(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    long long res = 0;
    if (l <= mid) res += query_range(p << 1, l, r);
    if (r > mid) res += query_range(p << 1 | 1, l, r);
    return res;
}

// 树上路径修改
void modify_path(int u, int v, long long val) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
        update_range(1, dfn[top[u]], dfn[u], val);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) std::swap(u, v);
    update_range(1, dfn[u], dfn[v], val);
}

// 树上路径求和查询
long long query_path(int u, int v) {
    long long total_sum = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
        total_sum += query_range(1, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) std::swap(u, v);
    total_sum += query_range(1, dfn[u], dfn[v]);
    return total_sum;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, root;
    if (!(std::cin >> n >> m >> root)) return 0;

    for (int i = 1; i <= n; ++i) std::cin >> w_init[i];

    for (int i = 1; i < n; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    tim = 0;
    dfs1(root, 0);
    dfs2(root, root);
    build(1, 1, n);

    for (int i = 0; i < m; ++i) {
        int opt, u, v;
        long long k;
        std::cin >> opt;
        if (opt == 1) { // 路径修改
            std::cin >> u >> v >> k;
            modify_path(u, v, k);
        } else if (opt == 2) { // 路径求和
            std::cin >> u >> v;
            std::cout << query_path(u, v) << "\n";
        } else if (opt == 3) { // 子树修改
            std::cin >> u >> k;
            update_range(1, dfn[u], dfn[u] + siz[u] - 1, k);
        } else if (opt == 4) { // 子树求和
            std::cin >> u;
            std::cout << query_range(1, dfn[u], dfn[u] + siz[u] - 1) << "\n";
        }
    }
    return 0;
}

NOIP 实战避坑指南

1. 线段树建树初始化映射错误： 在线段树 build 函数的叶子节点赋值阶段，很多选手习惯性写成 tree[p].sum = w_init[l]。这是严重的逻辑溃败。线段树维护的是拍平后的序列，位置 l 对应的原树节点是 rnki[l]，因此必须写成 tree[p].sum = w_init[rnki[l]]。
2. 线段树空间未开 4 倍： 树剖结构虽然没有增加节点，但与之绑定的线段树在开辟数组大小时，由于二叉树叶子节点的非满分布，数组大小必须严格开到 MAXN << 2（即 4 倍空间）。若只开了 1 倍或 2 倍空间，在 update_range 深度递归下传标记时，必然发生越界死锁或内存报负，导致赛场直接斩获 0 分。

经典 NOIP/洛谷 真题

1. 洛谷 P3384 【模板】重链剖分/树链剖分

• 题意描述： 给定一棵有根树，要求高效支持：路径加、路径求和、子树加、子树求和。
• 问题本质与核心思路： 这道题就是本章所讲解的“树剖 + 线段树”复合系统的经典纯净模板。核心思路是利用两遍 DFS 提取出重链拓扑，再利用线段树作为底层引擎去接管拍平后的连续区间。路径操作利用 while(top[u] != top[v]) 向上不断跳链，子树操作直接锁定单个区间 [dfn[u], dfn[u] + siz[u] - 1]。通过这套组合拳，四种高复杂度操作均能被完美平摊在 $O( ext{log}^2 N)$ 内解决。

2. 洛谷 P3979 遥远的国度

• 题意描述： 在一棵含有 $N$ 个节点的树上，支持路径修改、子树最小值查询。特殊之处在于，系统会动态修改当前的根节点位置。
• 问题本质与核心思路： 换根树剖问题。盲目重新跑剖分会导致复杂度暴崩，因此必须在线段树上分类讨论。 设当前全局动态根为 $ ext{root}$，要查询/修改的子树根为 $u$。

1. 若 $u == ext{root}$，则当前操作的子树就是整棵树，直接对整个线段树区间 $[1, N]$ 进行操作。
2. 若 $u$ 在以 $ ext{root}$ 为根的树中不是 $ ext{root}$ 的祖先，则 $u$ 的子树范围完全没有受到换根影响，依然操作线段树的连续区间 $[ ext{dfn}[u], ext{dfn}[u] + ext{siz}[u] - 1]$。
3. 若 $u$ 是 $ ext{root}$ 的祖先，此时以 $ ext{root}$ 为新根，原本 $u$ 的子树除了包含 $ ext{root}$ 的那个分支外，其余部分都被保留。我们可以利用树剖/倍增找到 $ ext{root}$ 向上跳到的 $u$ 的那个直系子节点 $v$。最终需要操作的区间就是除了 $v$ 的子树以外的所有节点，即在线段树上操作两个割裂的区间 $[1, ext{dfn}[v]-1]$ 和 $[ ext{dfn}[v] + ext{siz}[v], N]$。由此规避了动态换根的系统开销。