Graphs

Trees

Technique

Advanced

Heavy-Light Decomposition

Break tree paths into O(log n) heavy-chain segments so path queries can ride on top of a segment tree instead of walking edge by edge.

Trees is nested under Graphs , so techniques in the broader family usually still apply here.

tree

path-queries

segment-tree

rare

Interactive visualization

Use the controls to connect the idea to concrete operations before diving into the full write-up.

node	parent	depth	chain	base-array pos
0	-	0	A	0
1	0	1	A	1
2	0	1	C	5
3	1	2	A	2
4	1	2	B	4
5	2	2	C	6
6	3	3	A	3
7	5	3	C	7

Path broken into heavy-chain segments

chain C: [5, 7]

chain A: [0, 3]

Tree paths become a few array segments

Climb chain heads until both nodes share a chain, then each piece is just a segment-tree interval.

Family

Graphs → Trees

Hierarchies and constrained graphs. A tree is a connected acyclic graph.

Builds on

4 topics

Read these first if you want the surrounding context.

Unlocks

1 next topic

Use these follow-ups when you want to apply the current idea in a richer setting.

Learning paths

This topic appears in curated progressions so you can keep moving without guessing the next step.

Problem

Subtree queries are pleasant after an Euler tour because a subtree becomes one interval. Path queries are harder.

Examples:

sum along the path from u to v
maximum edge on a path
update every node on a path

A path is not usually one contiguous subtree interval, so you need another reduction.

Core idea

For every node, mark one child as heavy: usually the child with the largest subtree. The remaining child edges are light.

Heavy edges form disjoint chains. The key fact is:

any root-to-node path crosses only O(log n) light edges

So any path between two nodes can be decomposed into only O(log n) chain segments.

Once each chain is flattened into a base array, a segment tree can answer queries on each segment.

Query sketch

The usual pattern is:

while the chain heads of u and v differ
move the deeper chain head upward
query that whole chain segment in the base array
when both nodes land on the same chain, finish with one last contiguous segment

That turns one hard tree path into a small number of range queries.

Why it matters

Heavy-light decomposition is the path-query counterpart to Euler tour.

Euler tour is best when you care about subtrees
HLD is best when you care about paths

Together, they complete the mental model for turning trees into arrays.

Complexity

Operation	Time
Preprocessing decomposition	$O(n)$ or $O(n \log n)$ depending on implementation details
One path query/update with segment tree	$O(\log^2 n)$

With more specialized structures, some implementations reduce constants or one logarithm, but the classic version is $O(\log^2 n)$ .

Key takeaways

HLD is the standard reduction for path queries on trees
The win comes from crossing only O(log n) light edges
Segment trees usually sit underneath the decomposition
This is a rare advanced topic, but it is the natural next step after LCA and Euler tour

Practice problems

Problem	Difficulty	Key idea
Path Queries II	🔴 Hard	Classic HLD plus segment tree
Query on a tree again!	🔴 Hard	Edge/path queries with HLD
Cow Land	🔴 Hard	Tree path xor queries

Relation to other topics

Lowest Common Ancestor helps reason about path structure and split points
Euler Tour Technique solves subtree intervals, while HLD solves arbitrary path intervals
Segment Tree is the usual range structure placed on top of the decomposed chains
Persistent Segment Tree is one possible upgrade once ordinary HLD feels comfortable

Build on these first

These topics supply the mental model or underlying structure that this page assumes.

Graphs

Algorithm

DFS — Depth-First Search

Dive as deep as possible before backtracking. DFS is essential for detecting cycles, topological sorting, and exploring all paths in a graph.

Trees

Concept

Tree Fundamentals

Understand roots, parents, children, depth, height, and traversal orders. A tree is a graph with enough structure to make many problems much simpler.

Trees

Algorithm

Lowest Common Ancestor

Find the deepest shared ancestor of two nodes in a rooted tree. LCA is a core tree-query problem that ties together DFS, binary lifting, and Euler tours.

Range queries

Data structure