eduKate Sengkang

Small Group Tutorials

Here to help students catch up, keep up, and move ahead. Book a consultation here.

Chat on WhatsApp

How to Learn Heavy-Light Decomposition Algorithms: Heavy Edges, Tree Flattening, Path Queries and Segment Trees

Wait, What? A path inside a tree can be turned into only a small number of ordinary array intervals.

That is the idea behind heavy-light decomposition (HLD). It is not a new kind of tree. It is a way of organising an existing rooted tree so that difficult path queries become a sequence of familiar range queries. Once that representation is built, a segment tree, Fenwick tree or another range structure can do the arithmetic.

Quick Answer

Learn HLD in this order: rooted tree → subtree sizes → heavy child → light-edge halving → heavy paths → flattened positions → path decomposition → range data structure → updates → professional trade-offs. The central proof is simple and powerful: every time a root-to-node walk crosses a light edge, the remaining subtree becomes at most half as large, so there can be only O(log n) light-edge crossings.

1. Begin With the Problem HLD Solves

Suppose every vertex in a tree has a value. You are asked questions such as “What is the maximum value on the path from u to v?” or “Add 7 to every vertex on this path.” A naive solution walks along the path one vertex at a time. On a long chain that can cost O(n) per query.

Arrays are easier. If the same values lived in one contiguous array interval, a segment tree could answer or update that interval efficiently. HLD is the bridge: it maps tree paths to a small number of contiguous array ranges.

2. Root the Tree and Measure Subtrees

Choose a root. Run a depth-first search and record each vertex’s parent, depth and subtree size. For a vertex v, the subtree size s(v) is the number of vertices in the subtree rooted at v, including v itself.

This is the first important learning checkpoint. If a learner cannot compute subtree sizes correctly, HLD will feel mysterious later because the heavy edge is chosen from that information.

3. Mark One Child as Heavy

For each non-leaf vertex, choose the child with the largest subtree as the heavy child. The edge to that child is heavy. The other child edges are light. Some descriptions instead call an edge heavy when the child’s subtree is at least half the parent’s subtree. Both viewpoints lead to the property we care about: crossing a light edge sharply reduces the size of the remaining subtree.

4. Prove the Logarithmic Path Count

This is the proof worth learning rather than memorising. Suppose you move downward across a light edge from parent v to child c. Because c was not selected as the largest child, its subtree cannot remain more than half of the relevant size in the standard HLD argument. After one light edge the remaining subtree is at most about n/2; after two, n/4; after three, n/8. After O(log n) such halvings, only one vertex can remain.

Therefore a root-to-node path crosses only O(log n) light edges, and so it enters only O(log n) heavy paths. This is the engine behind the decomposition.

5. Flatten Heavy Paths Into an Array

Run a second traversal. Visit the heavy child first so that vertices belonging to the same heavy path receive consecutive positions in a base array. Record for every vertex:

  • its parent and depth;
  • its subtree size;
  • its heavy child;
  • the head of its current heavy path;
  • its position in the flattened array.

At this point the tree has not changed. Only its representation has. That distinction matters: HLD is a coordinate system over the tree.

6. Turn a Path Query Into Range Queries

To process a path between u and v, repeatedly compare the heads of their heavy paths. While the heads differ, move upward from the endpoint whose path head is deeper. Each move consumes one contiguous range in the base array, from that path head to the endpoint. Then jump to the parent of the path head.

Eventually u and v lie on the same heavy path. One final array interval completes the query. Because only O(log n) heavy paths are crossed, the original tree path becomes only O(log n) intervals.

7. Add a Segment Tree

If each interval query costs O(log n), and a tree path becomes O(log n) intervals, the straightforward HLD-plus-segment-tree design gives O(log² n) per path query or update. Some specialised problems can reduce this further using prefix information, stronger range structures or problem-specific algebra, but O(log² n) is the standard learning target.

8. Node Values and Edge Values Are Not the Same Mapping

For node-value queries, store each node’s value at its flattened position. For edge-value queries, a common convention stores an edge’s value at the position of its deeper endpoint. Then the lowest common ancestor needs careful treatment because the path edge entering the ancestor is not part of the answer. Many HLD bugs are not decomposition bugs at all; they are off-by-one mistakes caused by mixing node and edge conventions.

9. Direction Matters for Non-Commutative Operations

For sums, minima and maxima, combining segments in either direction gives the same result. For string concatenation, matrix multiplication, function composition or any other non-commutative operation, path direction matters. A professional implementation must preserve the order in which segments are traversed, often by maintaining forward and reverse aggregates or carefully stacking partial results.

10. HLD Is Not Automatically the Best Tree Technique

If queries are static and only ask for a lowest common ancestor, binary lifting or Euler-tour RMQ may be simpler. If a path sum never changes, prefix-style methods can be enough. If the topology itself changes dynamically, HLD on a fixed tree may not be the right abstraction. Algorithm selection begins with the workload, not with the prestige of the data structure.

Common Failure States

  • Choosing heavy edges before subtree sizes are correct.
  • Flattening light children before the heavy child and losing contiguous heavy paths.
  • Moving the shallower path head upward instead of the deeper one.
  • Mixing node-value and edge-value indexing.
  • Forgetting path direction for non-commutative aggregates.
  • Quoting O(log² n) without being able to explain where both logarithms come from.
  • Using HLD when a simpler static-tree technique already solves the problem.

A Learning Progression From Beginner to Professional

  • Beginner: trace subtree sizes and mark heavy children on a ten-node tree.
  • Developing: prove that each light edge reduces the remaining subtree enough to bound light crossings.
  • Intermediate: flatten heavy paths and answer a path maximum query by hand.
  • Advanced: implement point updates and path queries with one segment tree over the flattened array.
  • Professional: support lazy path updates, edge semantics, non-commutative aggregates, iterative traversals for deep trees, reproducible tests and memory-conscious layouts.

How to Test an Implementation

Do not begin with a giant random test. Start with small trees whose answers can be checked manually: a chain, a star, a balanced tree and a tree where many heavy-child ties occur. Compare HLD results against a slow path-walking reference implementation for hundreds of small random trees. This is a clean example of using a simple algorithm as an oracle for a faster one.

Why This Teaching Sequence Works

Novice programming research repeatedly shows that learners struggle when code composition arrives before a viable mental model. Worked examples and partial-completion tasks can reduce unnecessary cognitive load, while code tracing forces the learner to predict state changes. HLD is therefore best taught first as a labelled tree, then as a sequence of range transformations, and only then as code.

Sources and Further Reading

Professional rule: you understand heavy-light decomposition when you can derive the logarithmic path bound, map an arbitrary tree path into ordered array intervals, and explain when HLD is unnecessary.