Heavy-Light Decomposition vs Tree Chain Decomposition: Key Differences and Implementation Guide

Heavy-Light Decomposition (HLD) is a specific optimization of Tree Chain Decomposition (TCD) that uses subtree sizes to guarantee O(log N) chains per path query, while TCD represents the broader family of techniques for partitioning trees into linear segments.

In competitive programming and advanced algorithmic problem solving, path queries on trees require efficient decomposition strategies. The hzwer/shareoi repository contains educational resources comparing these approaches, specifically within files like 图论/树链剖分及其应用_蒋一瑶.pptx and 图论/树链剖分_王天懿.pptx, which illustrate how Heavy-Light Decomposition and Tree Chain Decomposition differ in their edge-selection heuristics and complexity guarantees.

Core Concepts: Definitions and Goals

Both techniques transform a rooted tree into a collection of vertex-disjoint paths (chains) to enable range queries via segment trees or Fenwick trees. However, their methodologies for selecting these chains diverge significantly.

What Is Heavy-Light Decomposition?

Heavy-Light Decomposition partitions a tree by marking, for each node, the child with the largest subtree size as the "heavy" child. All other children are "light." This size-based heuristic ensures that any root-to-leaf path crosses at most O(log N) light edges, bounding the number of chains visited during a query.

According to the algorithmic structure found in the shareoi materials, HLD implementations typically:

• Compute sz[v] (subtree sizes) in an initial DFS
• Select heavy[v] as the child maximizing subtree size
• Assign head[v] (chain head) and pos[v] (linearized index) in a second decomposition pass

What Is Tree Chain Decomposition?

Tree Chain Decomposition refers to the generic framework of cutting a tree into maximal chains without mandating a specific heuristic. As presented in 图论/树链剖分_王天懿.pptx, this approach may use alternative rules—such as splitting at every node with degree greater than two—to create chains that suit specific problem constraints, though without the logarithmic bound guarantee of HLD.

Heavy-Light Decomposition vs Tree Chain Decomposition: Technical Comparison

The distinctions between these methods affect preprocessing complexity, query performance, and implementation details.

Heavy Edge Selection Logic

The primary difference lies in how chains are formed:

• Heavy-Light Decomposition: Uses a size-based rule. In the dfs function, the implementation calculates sub=dfs(to,v) and updates heavy[v]=to only when sub>maxsz. This guarantees the heavy child represents more than half of the parent's subtree, ensuring the logarithmic chain property.

• Tree Chain Decomposition: Employs flexible heuristics. The example in the analysis uses a branching rule: if(children!=1) buildChains(to,to); else buildChains(to,h);. This starts a new chain whenever a node has more than one child, potentially creating more chains than HLD but with simpler logic.

Complexity and Performance Characteristics

Both approaches achieve O(N) preprocessing time, but their query behaviors differ:

Aspect	Heavy-Light Decomposition	Generic Tree Chain Decomposition
Preprocessing	O(N) for subtree sizes and chain assignment	O(N) for DFS order and chain heads
Path Query	O(log² N) – log N chains × log N segment tree operations	O(log² N) to O(N) depending on heuristic
Chain Count	At most O(N / log N) heavy chains	Variable, up to N chains if splitting frequently
Worst-case Chains per Query	O(log N) guaranteed	Depends on tree structure and heuristic

Implementation Structure

Both implementations maintain head[] and pos[] arrays for linearization, but differ in their construction logic:

Heavy-Light Decomposition (from the shareoi analysis):

int dfs(int v,int p){
    parent[v]=p; sz[v]=1; int maxsz=0;
    for(int to:g[v]) if(to!=p){
        depth[to]=depth[v]+1;
        int sub=dfs(to,v);
        sz[v]+=sub;
        if(sub>maxsz){ maxsz=sub; heavy[v]=to; }
    }
    return sz[v];
}

void decompose(int v,int h){
    head[v]=h; pos[v]=timer++;
    if(heavy[v]!=-1) decompose(heavy[v],h);
    for(int to:g[v]) if(to!=parent[v] && to!=heavy[v])
        decompose(to,to);
}

Tree Chain Decomposition (split-at-branching-nodes variant):

void buildChains(int v,int h){
    head[v]=h; pos[v]=timer++;
    int children = 0;
    for(int to:g[v]) if(to!=parent[v]) children++;
    for(int to:g[v]) if(to!=parent[v]){
        if(children!=1) buildChains(to,to); // new chain
        else buildChains(to,h);             // extend chain
    }
}

Source Material from the shareoi Repository

The hzwer/shareoi repository provides educational slide decks that contextualize these implementations:

• 图论/树链剖分及其应用_蒋一瑶.pptx: A comprehensive walkthrough covering the generic tree-chain decomposition technique, its construction, and applications including path queries and subtree aggregates.

• 图论/树链剖分_王天懿.pptx: A concise version focusing on algorithmic steps and example code snippets, illustrating the flexible chain construction rules.

• README.md: Organizes the repository structure, grouping these graph theory resources under the "图论" directory alongside string algorithms and dynamic programming materials.

These resources present Tree Chain Decomposition as the foundational concept, treating Heavy-Light Decomposition as the optimized variant that adds the size-based heuristic to achieve predictable logarithmic performance.

Summary

• Heavy-Light Decomposition is a specific instance of tree-chain decomposition that selects heavy edges based on subtree size to guarantee at most O(log N) chains are visited per path query.
• Tree Chain Decomposition is the broader algorithmic framework allowing arbitrary heuristics for chain formation, useful for educational purposes or custom partitioning needs.
• Both techniques linearize the tree using head[] and pos[] arrays and rely on segment trees or Fenwick trees for range operations.
• Implementations in the shareoi repository demonstrate that while the data structures remain identical, the chain-building logic determines whether you obtain the logarithmic worst-case guarantee of HLD or the flexible structure of generic TCD.

Frequently Asked Questions

Is Heavy-Light Decomposition just a type of Tree Chain Decomposition?

Yes. Heavy-Light Decomposition is a specific strategy within the Tree Chain Decomposition family. While TCD represents any method of partitioning a tree into linear chains, HLD specifically chooses the child with the largest subtree size as the continuation of the current chain. This size-based selection guarantees that any path from root to leaf crosses at most O(log N) distinct chains, making HLD the optimal choice for path query problems requiring strict complexity bounds.

Why does HLD guarantee O(log N) chains while generic TCD might not?

The guarantee stems from the heavy edge property: when a node always continues its chain through its largest child (the heavy child), any light edge (connecting to a smaller subtree) reduces the current subtree size by at least half. Consequently, a root-to-leaf path can contain at most log₂(N) light edges, each starting a new chain. Generic TCD might split chains at arbitrary points—such as every branching node—potentially creating up to N distinct chains in a star-shaped tree, leading to linear query times.

When should I use Tree Chain Decomposition instead of Heavy-Light Decomposition?

Use generic TCD when problem constraints allow simpler partitioning or when teaching the concept before introducing optimization heuristics. For example, if queries only ask about specific node types (like "nodes with degree > 2") or if the tree structure is guaranteed to be a path or shallow binary tree, a custom TCD rule may suffice. However, for general competitive programming problems involving arbitrary path sums or maximum queries on large trees (N ≤ 10⁵), HLD's logarithmic guarantee prevents worst-case time limit exceedances.

Where can I find canonical implementations of these algorithms?

The hzwer/shareoi repository contains authoritative educational materials in 图论/树链剖分及其应用_蒋一瑶.pptx and 图论/树链剖分_王天懿.pptx, which provide slide-based explanations and code structures. For production-ready C++ implementations, competitive programming libraries and the CP-algorithms website offer optimized versions using zero-based or one-based indexing with segment tree integration. The shareoi resources specifically emphasize the conceptual distinction between the generic decomposition framework and the heavy-light optimization.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}