Heavy-Light Decomposition (HLD) is a powerful technique that partitions a rooted tree into a set of disjoint paths (chains). This transformation allows for efficient range-based operations (like updates and queries) on tree structures by mapping the nodes into a linear array using a Segment Tree.

Core Definitions

• Heavy Edge: An edge connecting a parent node to the child with the largest subtree size.
• Heavy Child: The child node connected by a heavy edge.
• Light Edge/Child: Any edge or child not classified as "heavy."
• Heavy Chain: A sequence of heavy edges forming a path that descends through the tree.

Implementation Strategy

HLD requires two distinct Depth-First Search (DFS) traversals to prepare the tree structure:

1. First DFS: Calculates the parent, depth, subtree size, and identifies the heavy child for each node.
2. Second DFS: Maps each node to a position in a linear array (using a DFS order that prioritizes heavy children) and records the top node of the heavy chain for each node.

// Preprocessing: First pass to determine tree structure and heavy nodes
void computeSubtreeMetadata(int u, int p, int d) {
    depth[u] = d;
    parent[u] = p;
    subtreeSize[u] = 1;
    heavyChild[u] = -1;
    
    int maxSubtree = 0;
    for (int v : adj[u]) {
        if (v != p) {
            computeSubtreeMetadata(v, u, d + 1);
            subtreeSize[u] += subtreeSize[v];
            if (subtreeSize[v] > maxSubtree) {
                maxSubtree = subtreeSize[v];
                heavyChild[u] = v;
            }
        }
    }
}

// Preprocessing: Second pass to map nodes to linear order
void mapNodesToLinearOrder(int u, int chainTop) {
    chainHead[u] = chainTop;
    linearIndex[u] = ++timer;
    
    if (heavyChild[u] != -1) {
        mapNodesToLinearOrder(heavyChild[u], chainTop);
    }
    
    for (int v : adj[u]) {
        if (v != parent[u] && v != heavyChild[u]) {
            mapNodesToLinearOrder(v, v);
        }
    }
}

Path and Subtree Operations

By arranging the nodes such that heavy chains occupy contiguous segments in a linear array, we can use a Segment Tree to perform operations. For path queries or updates between nodes u and v, we traverse up the tree, hopping between chains until both nodes lie on the same chain. Since the index of nodes in the same chain is continuous, we apply the range operation via the Segment Tree.

void updatePath(int u, int v, int val) {
    while (chainHead[u] != chainHead[v]) {
        if (depth[chainHead[u]] < depth[chainHead[v]]) swap(u, v);
        segmentTree.modify(linearIndex[chainHead[u]], linearIndex[u], val);
        u = parent[chainHead[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    segmentTree.modify(linearIndex[u], linearIndex[v], val);
}

void updateSubtree(int u, int val) {
    // Subtree nodes occupy a contiguous range [linearIndex[u], linearIndex[u] + size[u] - 1]
    segmentTree.modify(linearIndex[u], linearIndex[u] + subtreeSize[u] - 1, val);
}

The total time complexity for each query or update operation is O(log²n), as we traverse at most O(log n) heavy chains, and each segment tree operation takes O(log n).