Heavy Light Decomposition: Complete Implementation Guide

1. Introduction and Core Concepts

Heavy Light Decomposition (HLD) is one of the most powerful techniques for handling path and subtree queries on trees. It transforms a tree structure into a collection of linear chains such that any root-to-leaf path intersects only a logarithmic number of chains. By linearizing the tree in this clever way, HLD allows us to leverage classic array-based data structures like segment trees and Fenwick trees to answer complex tree queries efficiently.

At its core, heavy light decomposition is not a data structure itself, but a decomposition strategy. It reorders the nodes of a tree into an array (often called the base array or position array) where nodes belonging to the same heavy path occupy contiguous segments. Once this mapping is established, any operation on a tree path — such as finding the sum, minimum, maximum, or greatest common divisor of node values along the path — can be reduced to a series of range queries on these contiguous segments.

The importance of heavy light decomposition stems from its ability to solve problems that are otherwise difficult to handle efficiently. A naive approach to a path query between two nodes u and v might walk up the tree node by node, resulting in O(N) time per query. For trees with up to 10^5 or 10^6 nodes and an equal number of queries, this is prohibitively slow. HLD reduces this to O(log^2 N) per query, making it feasible for competitive programming, large-scale network analysis, and database query optimization on hierarchical data.

Why Heavy Light Decomposition Matters

The key insight behind HLD is the distinction between heavy and light edges. For every non-leaf node, we identify its heavy child — the child with the largest subtree size. The edge to this child is classified as heavy, while all other edges to children are light. Heavy edges are then stitched together to form heavy paths or chains. This simple classification guarantees a crucial property: any path from the root to any node traverses at most O(log N) light edges, and therefore at most O(log N) heavy paths.

This logarithmic bound is what makes HLD so efficient. Unlike naive tree traversals, we can jump from chain to chain using segment tree operations, each taking O(log N) time. The combination yields O(log^2 N) per path operation, which can often be optimized to O(log N) with careful implementation or using a Fenwick tree for invertible operations like sum.

Core Terminology

To understand HLD, you must be familiar with several key terms. The subtree size of a node is the number of nodes in its subtree, including itself. The heavy child is the child with maximum subtree size (ties broken arbitrarily). The head of a chain is the topmost node of that heavy path, which is always a light child of its parent or the root. The position (pos) or dfs-order index is the linear index assigned to each node in the base array, and parent and depth arrays store standard tree information computed during the initial DFS.

2. How It Works

Heavy light decomposition operates in two distinct depth-first search passes. The first DFS computes essential metadata for every node: its subtree size, parent, depth, and heavy child. This pass is a standard post-order traversal where the size of a node is computed as one plus the sum of sizes of its children. While computing these sizes, we simultaneously track which child is the heaviest.

The second DFS is responsible for the actual decomposition. It traverses the tree by prioritizing heavy edges. Starting from the root, it follows the heavy path as far as possible, assigning the same chain head to all nodes on that path and giving them consecutive positions in the base array. When it encounters a light child, it starts a new chain with that light child as its head. This ensures that nodes on the same heavy path are contiguous in the linearized array, while light subtrees are placed elsewhere but still maintain their internal heavy-path contiguity.

Once the decomposition is complete, any path query between nodes u and v can be answered by climbing the chains. The algorithm repeatedly compares the heads of the chains containing u and v. The deeper head is processed first: we query the segment tree over the range from the head's position to the node's position, then jump the node to the parent of the head. This continues until both nodes are on the same chain, at which point a single final range query between their positions completes the operation. This chain-jumping mechanism is the heart of HLD's efficiency.

The Heavy-Light Property

The fundamental theorem that makes HLD work is that the number of light edges on any root-to-leaf path is at most log2 N. To see why, consider moving from a node to its light child. By definition, the light child's subtree size is at most half of its parent's subtree size (otherwise it would be the heavy child). Therefore, each time we traverse a light edge downward, the subtree size at least halves. Since we start with size N at the root and cannot go below 1, we can halve at most log2 N times. This property guarantees that any path between two arbitrary nodes, which can be split into two root-to-node paths, will intersect at most 2 * log N chains.

Linearization and the Base Array

The base array is the bridge between the tree world and the array world. After decomposition, we create an array baseArray where baseArray[pos[u]] = value[u] for each node u. All segment tree or Fenwick tree operations are performed on this baseArray. For subtree queries, HLD offers an additional bonus: the entire subtree of a node u corresponds to a contiguous range [pos[u], pos[u] + size[u] - 1] in the base array, because the decomposition DFS processes a node's entire heavy path before exploring light subtrees. This means subtree queries become a single range query, even simpler than path queries.

3. Implementation

Implementing heavy light decomposition correctly requires careful handling of recursion, indexing, and the integration with a segment tree. Below is a complete, production-ready Python implementation broken into modular components. We use iterative recursion limits and 0-based or 1-based indexing consistently. For large trees (N > 10^5), consider increasing recursion limit or using iterative DFS to avoid stack overflow in Python.

The implementation consists of four parts: first DFS to compute sizes and heavy children, second DFS to decompose and assign heads and positions, a segment tree for range queries, and the HLD query/update interface. We will use 0-based indexing for nodes and positions for simplicity, but the logic translates directly to 1-based.

Part 1: First DFS - Computing Sizes and Heavy Child

import sys
sys.setrecursionlimit(300000)

class HeavyLightDecomposition:
    def __init__(self, n, adj, values):
        self.n = n
        self.adj = adj
        self.values = values
        self.parent = [-1] * n
        self.depth = [0] * n
        self.size = [0] * n
        self.heavy = [-1] * n  # heavy child of each node
        self.head = [0] * n    # head of the chain
        self.pos = [0] * n     # position in base array
        self.cur_pos = 0
        self.base_array = [0] * n

        # First DFS: compute sizes and heavy child
        self._dfs(0, -1)
        # Second DFS: decompose into chains
        self._decompose(0, 0)
        # Build segment tree over base array
        self.seg = SegmentTree(self.base_array)

    def _dfs(self, u, p):
        """Compute subtree sizes and identify heavy child."""
        self.size[u] = 1
        max_subtree = 0
        self.parent[u] = p
        for v in self.adj[u]:
            if v != p:
                self.depth[v] = self.depth[u] + 1
                self._dfs(v, u)
                self.size[u] += self.size[v]
                # Track heaviest child
                if self.size[v] > max_subtree:
                    max_subtree = self.size[v]
                    self.heavy[u] = v

Part 2: Second DFS - Decomposition and Linearization

    def _decompose(self, u, h):
        """Assign head and position, build base array."""
        self.head[u] = h
        self.pos[u] = self.cur_pos
        self.base_array[self.cur_pos] = self.values[u]
        self.cur_pos += 1

        # First, continue down the heavy path to keep it contiguous
        if self.heavy[u] != -1:
            self._decompose(self.heavy[u], h)

        # Then, decompose each light child as a new chain
        for v in self.adj[u]:
            if v != self.parent[u] and v != self.heavy[u]:
                self._decompose(v, v)  # new head is itself

Part 3: Segment Tree for Range Queries

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [0] * (2 * self.size)
        # Build leaves
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        # Build internal nodes (sum example)
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def point_update(self, idx, value):
        """Set position idx to value."""
        i = self.size + idx
        self.tree[i] = value
        i //= 2
        while i >= 1:
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
            i //= 2

    def range_query(self, l, r):
        """Inclusive range sum query [l, r]."""
        l += self.size
        r += self.size
        res = 0
        while l <= r:
            if l % 2 == 1:
                res += self.tree[l]
                l += 1
            if r % 2 == 0:
                res += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return res

Part 4: Path Queries and Updates Using HLD

    # Continuing HeavyLightDecomposition class...

    def query_path(self, u, v):
        """Query sum on path from u to v."""
        res = 0
        while self.head[u] != self.head[v]:
            # Always climb from deeper head
            if self.depth[self.head[u]] < self.depth[self.head[v]]:
                u, v = v, u
            # Query the entire chain segment from head[u] to u
            cur_head = self.head[u]
            res += self.seg.range_query(self.pos[cur_head], self.pos[u])
            u = self.parent[cur_head]
        # Now u and v are on same chain
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        # Query remaining segment (u is LCA)
        res += self.seg.range_query(self.pos[u], self.pos[v])
        return res

    def update_node(self, u, value):
        """Update value of single node u."""
        self.seg.point_update(self.pos[u], value)

    def query_subtree(self, u):
        """Query sum of subtree rooted at u."""
        return self.seg.range_query(self.pos[u], self.pos[u] + self.size[u] - 1)

    def lca(self, u, v):
        """Find LCA using HLD heads (alternative to binary lifting)."""
        while self.head[u] != self.head[v]:
            if self.depth[self.head[u]] > self.depth[self.head[v]]:
                u = self.parent[self.head[u]]
            else:
                v = self.parent[self.head[v]]
        return u if self.depth[u] < self.depth[v] else v

This implementation supports path sum queries, point updates, subtree queries, and LCA in logarithmic time. To support other operations like range maximum, minimum, or GCD, simply change the segment tree's combine function from addition to max, min, or math.gcd. For range updates (e.g., add value to all nodes on a path), replace the segment tree with a lazy propagation segment tree.

4. Step-by-Step Example

Consider a tree with 9 nodes labeled 0 to 8, rooted at 0. Edges are: 0-1, 0-2, 1-3, 1-4, 2-5, 2-6, 5-7, 5-8. Node values are [5, 3, 8, 2, 4, 6, 1, 9, 7] for nodes 0 through 8 respectively. We will walk through the complete decomposition process.

First DFS computes subtree sizes. Leaves 3, 4, 6, 7, 8 have size 1. Node 5 has children 7 and 8, so size[5] = 1 + 1 + 1 = 3. Node 1 has children 3 and 4, so size[1] = 1 + 1 + 1 = 3. Node 2 has children 5 and 6, so size[2] = 1 + 3 + 1 = 5. Root 0 has children 1 and 2, so size[0] = 1 + 3 + 5 = 9. For heavy children: for node 0, child 2 (size 5) > child 1 (size 3), so heavy[0] = 2. For node 1, both children size 1, pick 3 as heavy (tie-break). For node 2, child 5 (size 3) > child 6 (size 1), so heavy[2] = 5. For node 5, pick 7 as heavy.

Second DFS decomposes. Start at root 0 with head 0. pos[0]=0, follow heavy to 2 (same head 0), pos[2]=1, follow heavy to 5 (same head 0), pos[5]=2, follow heavy to 7 (same head 0), pos[7]=3. Node 7 has no heavy child, backtrack. Node 5's light child 8 starts new chain head 8, pos[8]=4. Back to node 2, light child 6 starts new chain head 6, pos[6]=5. Back to root 0, light child 1 starts new chain head 1, pos[1]=6, follow heavy to 3 (same head 1), pos[3]=7, then light child 4 starts new chain head 4, pos[4]=8. The base array becomes [5, 8, 6, 9, 7, 1, 3, 2, 4] corresponding to node order [0,2,5,7,8,6,1,3,4].

Executing a Path Query

Now query the sum on path from node 4 to node 8. Path is 4 -> 1 -> 0 -> 2 -> 5 -> 8, values 4+3+5+8+6+7 = 33. Using HLD: Initially head[4]=4, head[8]=8, depth[head[4]]=2, depth[head[8]]=3, so head[8] is deeper. Query segment [pos[8], pos[8]] = [4,4] -> value 7. Jump 8 to parent[8]=5. Now head[4]=4, head[5]=0, depth[4]=2 > depth[0]=0, so query [pos[4], pos[4]]? Wait head[4]=4, so query [pos[4], pos[4]] is not correct; actually u=4, head[4]=4, query [pos[4], pos[4]] = [8,8] -> 4, jump 4 to parent[4]=1. Now u=1 (head 1), v=5 (head 0), head[1] depth 1 > head[0] depth 0, query [pos[1], pos[1]]? Actually chain head 1 contains nodes 1 and 3, pos[1]=6, pos[4]'s sibling was already processed, now u=1, query [pos[1], pos[1]] = [6,6] -> 3, jump 1 to parent[1]=0. Now u=0 (head 0), v=5 (head 0) same chain! Query [pos[0], pos[5]] = [0,2] -> 5+8+6=19. Total = 7+4+3+19=33, correct.

This example demonstrates how a path that would naively require traversing 6 nodes is broken into 4 segment tree queries, each O(log N). For larger trees, the number of segments remains logarithmic, ensuring scalability.

5. Complexity Analysis

Understanding the time and space complexity of heavy light decomposition is essential for determining when to apply it and how it will perform under different constraints. The analysis separates preprocessing (building the decomposition) from query operations, as they have distinct characteristics.

Preprocessing consists of two DFS traversals, each visiting every node and edge exactly once, resulting in O(N) time. The segment tree construction over the base array also takes O(N) time. This linear preprocessing is a one-time cost and is highly efficient. Space consumption is also linear: we store several arrays of size N (parent, depth, size, heavy, head, pos, baseArray) plus the segment tree which requires up to 4*N or 2*pow2(N) space depending on implementation. Overall space is O(N).

For queries, the complexity depends on the operation. A path query or path update between two nodes u and v traverses at most O(log N) chains, and each chain segment query/update on the segment tree costs O(log N), yielding O(log^2 N) total. Subtree queries are faster — only O(log N) — because a subtree maps to a single contiguous segment. LCA via HLD is O(log N) as it only climbs heads without segment tree queries. If the segment tree operation is invertible and we use a Fenwick tree instead, path queries can be optimized to O(log N) in some cases, but the general bound remains O(log^2 N).

It is important to note that the worst-case path query occurs when the path alternates frequently between heavy and light edges, such as in a caterpillar tree or a balanced binary tree where heavy paths are short. Even in this worst case, the logarithmic bound holds. The best case for a path query is when both nodes lie on the same heavy path, requiring only a single segment tree query O(log N). For star trees, HLD degrades gracefully: the root's heavy child is one leaf, all other leaves are light chains of length one, and any leaf-to-leaf path still only traverses O(1) chains via the root.

6. Variations and Optimizations

While the classic HLD implementation is powerful, several variations and optimizations adapt it to specific problem constraints and improve constant factors. One common optimization is to use iterative DFS instead of recursion to avoid Python recursion limits and stack overflow for deep trees (e.g., a line tree with 200,000 nodes). Another is to use an Euler tour ordering combined with HLD to support both path and subtree queries simultaneously without extra overhead.

For problems requiring range updates on paths (e.g., add 5 to every node on path u-v), the segment tree must support lazy propagation. The HLD logic remains identical; only the underlying data structure changes to a lazy segment tree that can handle range add and range query in O(log N) per segment. Similarly, for operations that are not easily invertible like maximum or minimum, a segment tree is mandatory, while for sum or XOR, a Fenwick tree (Binary Indexed Tree) can be used for slightly better constant factors and simpler code.

An advanced variation is Heavy Light Decomposition with binary lifting hybrid. While HLD can answer LCA queries in O(log N), binary lifting answers LCA in O(log N) with lower constants and also supports k-th ancestor queries. Many implementations therefore combine HLD for path queries with a separate binary lifting table for LCA and ancestor jumps, getting the best of both worlds.

Optimization Techniques

To reduce the O(log^2 N) factor to O(log N) for path queries, some implementations use a segment tree that can answer queries over multiple disjoint intervals faster, or they use a technique called long path decomposition where heavy paths are chosen by height rather than size. Another micro-optimization is to store the base array values directly in the segment tree without a separate array, and to use iterative segment tree loops with bit operations for speed.

Memory optimization is also relevant for large N. Instead of storing 6-7 integer arrays, you can compress parent and heavy into a single array or reuse the adjacency list after DFS. In languages like C++ this matters more, but in Python, using lists of ints and PyPy's fast I/O is usually sufficient for N up to 200,000.

Alternative Decomposition Strategies

Beyond standard HLD, there are related decompositions. Centroid decomposition is better for distance-based queries and path queries that involve counting nodes within distance K. Euler Tour + Mo's Algorithm on Trees can handle offline path queries with more complex, non-decomposable functions but with higher complexity O((N+Q) * sqrt(N)). Choosing the right decomposition depends on whether queries are online or offline, and whether updates are required.

7. Real-World Applications

Although heavy light decomposition is most famous in competitive programming, its principles are applied in several real-world systems that manage hierarchical or tree-structured data. Any domain where data is organized as a tree and requires frequent path or subtree aggregations can benefit from HLD or its conceptual variants.

In network routing and telecommunications, the network topology is often modeled as a tree (e.g., spanning tree of a larger graph). Queries such as finding the maximum latency or minimum bandwidth along the path between two routers, or updating link costs, are exactly path queries that HLD accelerates. Similarly, in file systems and version control, directory structures are trees. Operations like computing the total size of a directory (subtree sum) or finding the most recently modified file on the path from root to a file can be optimized with HLD-like linearization.

In databases and query optimizers, hierarchical data such as organizational charts, category trees in e-commerce, or XML/JSON document trees are common. SQL extensions for hierarchical queries (e.g., WITH RECURSIVE) can be accelerated by preprocessing the tree with HLD and using indexed range queries. Web servers and content delivery networks that manage cache hierarchies also use tree path queries to determine cache invalidation paths or to aggregate access statistics along the path from edge server to origin.

In game development, skeletal animation systems represent character skeletons as trees of bones. Updating world transforms requires propagating changes from root to leaves along bone chains — a classic path update problem. HLD allows batch updates to be applied efficiently. In computational biology, phylogenetic trees with millions of nodes require fast queries for evolutionary distances and common ancestors, where HLD-based LCA and path queries are invaluable.

8. Comparison with Alternatives

Heavy light decomposition is not the only technique for tree queries. The choice depends on query type, whether updates are needed, and whether queries are online or offline. Understanding the trade-offs helps you select the most appropriate tool for a given problem.

For static trees with no updates and only LCA queries, binary lifting is simpler and faster. For subtree-only queries, a single Euler tour with a Fenwick tree suffices — HLD is overkill. For path queries with offline processing and complex functions, Mo's algorithm on trees might be more flexible. For dynamic trees where edges are cut and linked (dynamic forest), Link-Cut Trees (LCT) or Euler Tour Trees are required, as HLD only supports static tree structures (though it supports value updates, not structural changes).

In practice, many competitive programmers learn HLD as the go-to for any path query problem on static trees because it is more versatile than Euler tour alone and far simpler to implement correctly than a Link-Cut Tree. If you only need LCA, binary lifting is preferable due to its simplicity and ability to answer k-th ancestor queries. If you need to handle a fully dynamic forest where edges are added and removed online, you must invest in Link-Cut Trees, which are significantly more complex and have higher constant factors.

9. Common Mistakes and Best Practices

Implementing heavy light decomposition is error-prone, especially under contest pressure. One of the most frequent mistakes is inconsistent indexing between 0-based and 1-based nodes and positions. If the input nodes are 1-indexed but your arrays are 0-indexed, off-by-one errors in segment tree queries will produce wrong answers that are hard to debug. Always decide on a convention at the start and convert input accordingly.

Another common pitfall is forgetting to handle the final segment when both nodes are on the same chain. The while loop that climbs chains terminates when heads are equal, but you must still query the segment between the two nodes (ordered by depth). Omitting this last query or querying in the wrong order (e.g., [pos[v], pos[u]] when pos[v] > pos[u]) leads to incorrect results or out-of-bounds queries. Always ensure l <= r in your range query.

Recursion depth is a serious issue in Python. A degenerate tree that is a straight line of 200,000 nodes will cause recursion depth errors even with sys.setrecursionlimit increased, and may cause stack overflow or recursion limit crashes. Best practice is to implement DFS iteratively using an explicit stack, or to use PyPy with increased recursion limit and hope the tree is not adversarial. For production code, iterative is safer.

Best Practices for Robust Code

Always test your HLD implementation on small, hand-crafted trees including edge cases: a single node tree, a line tree (chain), a star tree, and a balanced binary tree. Verify path queries against a brute-force naive implementation for random trees and random queries in a stress test. This catches subtle bugs in head assignment or position ordering.

When building the segment tree, be explicit about whether your range queries are inclusive or exclusive. The code above uses inclusive [l, r], but many templates use half-open [l, r). Mixing conventions between HLD and segment tree is a frequent source of bugs. Document your convention clearly.

For performance, use fast I/O (sys.stdin.buffer.read) in Python for large inputs, and consider using iterative segment trees with arrays rather than recursive segment tree functions, which add overhead. If you need range updates, implement lazy propagation correctly and test it thoroughly with overlapping updates. Finally, keep your HLD class modular: separate the decomposition logic from the segment tree logic so you can swap the underlying data structure (sum, max, min, GCD) without rewriting the decomposition.

• Double-check parent of chain head jumps: u = parent[head[u]], not parent[u], otherwise you may stay on same chain.
• Ensure depth comparison uses head depths, not node depths, when deciding which chain to process.
• Initialize heavy array to -1 and check for -1 before recursing on heavy child.
• Use iterative DFS for N > 10^5 to avoid recursion limits in Python.
• Stress test against brute force for at least 1000 random queries before submitting.

10. Interview Questions

Heavy light decomposition is a favorite topic for advanced algorithm interviews at top technology companies and for competitive programming contests. Interviewers use it to assess understanding of tree algorithms, decomposition techniques, and the ability to combine data structures. Below are common questions and how to approach them.

Q1: How would you find the maximum edge weight on the path between two nodes with updates?

This is the classic HLD application. Explain that you would store edge weights in the child node's position (or use edge-based HLD where baseArray[pos[child]] = weight(parent-child)). Build a segment tree for range maximum. For query(u, v), climb chains as described, querying max on each segment and taking overall max. Point updates are O(log N) by updating the child node's position. Emphasize the heavy-light property guaranteeing O(log^2 N) per query and discuss how to handle the LCA edge exclusion if needed.

Q2: Can HLD handle subtree queries? How does it compare to Euler Tour?

Yes, HLD naturally supports subtree queries because each subtree corresponds to a contiguous interval [pos[u], pos[u]+size[u]-1]. This is actually simpler than path queries and requires only one segment tree query O(log N). Euler Tour (flattening via entry/exit times) also supports subtree queries with one range query and is simpler to implement if only subtree queries are needed. HLD's advantage is that it supports both path and subtree queries with the same decomposition, while Euler Tour alone cannot handle path queries efficiently.

Q3: What is the time complexity of HLD and why is it O(log^2 N) for path queries?

Expect to explain the two logarithmic factors: one from the number of chains visited (at most O(log N) light edges on any root-to-leaf path) and one from the segment tree query per chain (O(log N)). Detail the proof that light edges halve subtree size, leading to the O(log N) chain bound. Also mention that subtree queries are O(log N) and preprocessing is O(N). Bonus points for mentioning that with a Fenwick tree and invertible operations, or with careful optimization, path queries can be O(log N) in practice.

Q4: How would you modify HLD to support adding a value to all nodes on a path?

This requires a lazy propagation segment tree. The HLD climbing logic stays identical, but instead of range queries, you perform range updates (add value to interval [pos[head[u]], pos[u]]) on each chain segment. Each segment update is O(log N) with lazy propagation, so total is O(log^2 N). For queries after updates, the segment tree must propagate lazy values correctly. Discuss the difference between point updates and range updates, and why lazy propagation is necessary to keep O(log N) per segment.

Q5: When would you choose Link-Cut Tree over HLD?

Answer: When the tree structure itself is dynamic — edges are being cut and linked (dynamic forest) — HLD cannot handle it because its decomposition is static and based on initial subtree sizes. Link-Cut Trees support link, cut, path queries, and evert operations in O(log N) amortized time using splay trees and preferred paths. However, LCT is far more complex to implement, has higher constant factors, and is overkill for static trees. For static trees with only value updates, HLD is simpler, faster in practice, and easier to debug, so it should be preferred.

Preparing for these questions involves not just memorizing the code, but understanding the underlying invariants, being able to walk through an example on a whiteboard, and discussing trade-offs with alternative approaches. Interviewers often ask you to code the DFS and decomposition functions from scratch, so practice writing them without reference.