Efficient Path Operations and Subtree Maintenance Using Heavy Chain Decomposition and Segment Trees

Core Logic and Mathematical Principles

This chapter tightly couples heavy chain decomposition of trees with segment trees to address the complex problems of path modifications, subtree maintenance, and composite logic retrieval in industrial-grade, high-concurrency scenarios. The core mathematical foundation lies in the interval overlap and independence of topological mapping.

Through heavy chain decomposition, two key spatial domains on the tree are perfectly isomorphic to the linear leaf node intervals of the segment tree $[1, N]$:

Path Domain Mapping: Any path $(u, v)$ is divided into at most $O( ext{log} N)$ segments of continuous decomposition intervals. Each segment corresponds to one or more nodes in the segment tree, and by utilizing lazy propagation, we can strictly limit the time complexity of path modifications and queries to $O( ext{log}^2 N)$.
Subtree Domain Mapping: The subtree rooted at $u$ corresponds to a strictly continuous closed interval $[ ext{dfn}[u], ext{dfn}[u] + ext{siz}[u] - 1]$ in the decomposition order. For overall modifications and queries of the subtree, only one interval operation is needed in the segment tree, with a time complexity of $O( ext{log} N)$.

Algorithm Derivation and State Design

Designing a complete system that combines tree decomposition and segment trees requires maintaining two sets of states.

1. Segment Tree State Design

For the flattened sequence $ ext{rnki}[i]$ (which indicates the original tree node number corresponding to the $i^{th}$ position in the new sequence), the structure of the segment tree node is defined as follows:

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

State Transition Equation (PushUp):

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

Lazy Propagation Equation (PushDown): If $ ext{tree}[p]. ext{lazy} eq 0$, for the left and right child nodes $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)$$

The same applies to the right child node, and after propagation, $ ext{tree}[p]. ext{lazy} = 0$.

2. Path Modification and Query Derivation on Trees

For querying/modifying the path $(u, v)$:

Compare the topological depths of the two endpoints $ ext{dep}[ ext{top}[u]]$ and $ ext{dep}[ ext{top}[v]]$.
Without loss of generality, assume $ ext{dep}[ ext{top}[u]] ext{ }\ge ext{ }\text{dep}[ ext{top}[v]]$, at this point, the heavy chain containing $u$ is deeper overall. Perform operations on the segment tree interval $[ ext{dfn}[ ext{top}[u]], ext{dfn}[u]]$.
Set $u = ext{fa}[ ext{top}[u]]$, exiting the current heavy chain and entering the upper level of the topological structure.
Repeat steps 1-3 until $ ext{top}[u] == ext{top}[v]$.
At this point, both endpoints are on the same heavy chain, and finally perform a concluding operation on the segment tree interval $[ ext{min}( ext{dfn}[u], ext{dfn}[v]), ext{max}( ext{dfn}[u], ext{dfn}[v])]$.

C++ Standard Source Code

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

const int MAXN = 100005;

// Tree topology structure
std::vector<int> adj[MAXN];
int w_init[MAXN]; // Initial weights of original tree nodes
int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN];
int top[MAXN], dfn[MAXN], rnki[MAXN], tim;

// Core structure of segment tree
struct SegTree {
    int l, r;
    long long sum;
    long long lazy;
} tree[MAXN << 2];

// First DFS for tree decomposition
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;
        }
    }
}

// Second DFS for tree decomposition
void dfs2(int u, int t) {
    top[u] = t;
    tim++;
    dfn[u] = tim;
    rnki[tim] = u;
    if (!son[u]) return;
    dfs2(son[u], t); // Prioritize heavy child
    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);
    }
}

// Basic driving functions for the segment tree
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]]; // Critical point: must use new sequence index to map back to original tree node weights
        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;
}

// Modify path on the tree
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);
}

// Query sum along the path on the tree
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) { // Path modification
            std::cin >> u >> v >> k;
            modify_path(u, v, k);
        } else if (opt == 2) { // Path sum query
            std::cin >> u >> v;
            std::cout << query_path(u, v) << "\n";
        } else if (opt == 3) { // Subtree modification
            std::cin >> u >> k;
            update_range(1, dfn[u], dfn[u] + siz[u] - 1, k);
        } else if (opt == 4) { // Subtree sum query
            std::cin >> u;
            std::cout << query_range(1, dfn[u], dfn[u] + siz[u] - 1) << "\n";
        }
    }
    return 0;
}

Practical Pitfalls Guide for NOIP

Incorrect Initialization Mapping in Segment Tree Construction: During the leaf node assignment phase of the segment tree build function, many contestants habitually write tree[p].sum = w_init[l]. This is a serious logical failure. The segment tree maintains the flattened sequence, and the position l corresponds to the original tree node rnki[l], so it must be written as tree[p].sum = w_init[rnki[l]].
Segment Tree Space Not Allocated to 4 Times: Although the tree decomposition does not increase the number of nodes, the segment tree associated with it must strictly allocate the array size to MAXN << 2 (i.e., 4 times the space) due to the non-full distribution of leaf nodes in the binary tree. If only 1 or 2 times the space is allocated, deep recursive propagation of the update_range will inevitably cause out-of-bounds deadlocks or memory overflow, resulting in a score of 0 in the competition.

Classic NOIP/Luogu Problems

1. Luogu P3384 [Template] Heavy Chain Decomposition/Tree Chain Decomposition

Problem Statement: Given a rooted tree, efficiently support: path addition, path sum, subtree addition, and subtree sum.
Core Idea and Essence of the Problem: This problem is a classic pure template of the "tree decomposition + segment tree" composite system discussed in this chapter. The core idea is to utilize two DFS passes to extract the heavy chain topology, and then use the segment tree as the underlying engine to manage the flattened continuous intervals. Path operations utilize while(top[u] != top[v]) to continuously jump chains upwards, while subtree operations directly lock onto a single interval [dfn[u], dfn[u] + siz[u] - 1]. Through this combination, four high-complexity operations can be perfectly amortized within $O( ext{log}^2 N)$.

2. Luogu P3979 The Distant Kingdom

Problem Statement: On a tree with $N$ nodes, support path modifications and subtree minimum queries. The special aspect is that the system will dynamically modify the current root node position.
Core Idea and Essence of the Problem: This is a root-switching tree decomposition problem. Blindly rerunning the decomposition will lead to a collapse in complexity, so it must be discussed categorically on the segment tree. Let the current global dynamic root be $ ext{root}$, and the subtree root to be queried/modified be $u$.

If $u == ext{root}$, then the current operation's subtree is the entire tree, directly operating on the entire segment tree interval $[1, N]$.
If $u$ is not an ancestor of $ ext{root}$ in the tree rooted at $ ext{root}$, then the subtree range of $u$ is completely unaffected by the root switch, still operating on the continuous segment tree interval $[ ext{dfn}[u], ext{dfn}[u] + ext{siz}[u] - 1]$.
If $u$ is an ancestor of $ ext{root}$, then with $ ext{root}$ as the new root, the subtree of $u$ retains all parts except the branch containing $ ext{root}$. We can use tree decomposition or binary lifting to find the direct child node $v$ that $ ext{root}$ jumps up to in $u$. The final intervals to operate on are two disjoint segments on the segment tree: $[1, ext{dfn}[v]-1]$ and $[ ext{dfn}[v] + ext{siz}[v], N]$. This avoids the overhead of dynamic root switching.