Loading…

hardTreesRarely asked

Heavy-Light Decomposition (Path Queries)

Q: How do you solve Heavy-Light Decomposition (Path Queries) using the Baseline — Walk the Path via the LCA approach?

When to use it: Say this first: it is the obvious correct method and shows why long paths force a smarter layout. The direct method needs only parent pointers, depths, and per-node values. **Find the meeting point.** Compute `lca(u, v)`. The path from `u` to `v` is `u → … → lca → … → v`. **Walk and aggregate.** Step `u` upward to the LCA, combining each node's value; do the same for `v`; include the LCA once. The combine is whatever the query asks (sum, max, …). **Why it is correct.** Every node on the `u`-to-`v` path is on one of the two upward walks to their LCA, and the LCA is the single shared top. **Why it is too slow.** A path can span the entire height of the tree — O(n) for a chain. Answering 10⁵ such queries is O(n·q). The remedy is to relabel nodes so that the path decomposes into a *few* contiguous ranges that a segment tree aggregates in logarithmic time — which is exactly what HLD provides. Time complexity: O(n) per query, O(1) update. Space complexity: O(n).

Trees & BST · 28 of 41 · 13 min

You are given a rooted tree with n nodes, each holding a value. Support many queries of the form:

1
**pathQuery(u, v)** — aggregate (e.g. sum or max) of the values on the path from u to v.
2
**update(node, val)** — change the value at a node.

The tree's shape is fixed. Use heavy-light decomposition with a segment tree so each path query runs in **O(log² n)** and each update in **O(log n)**.

In plain English

Subtree problems flatten cleanly with an Euler tour, but a path between two arbitrary nodes is not contiguous in DFS order. HLD fixes this by cutting the tree into chains along 'heavy' edges (toward the largest child) and laying each chain contiguously. The decomposition guarantees any root-to-node path touches only O(log n) chains, so a path becomes O(log n) contiguous ranges — exactly what a segment tree handles.

Examples

Example 1

Input: path tree 0-1-2-3-4 (a chain), values=[1,2,3,4,5]; pathQuery(0,4) sum
Output: 15
Note: A chain is a single heavy path, so the whole path is one contiguous segment-tree range: 1+2+3+4+5 = 15.

Example 2

Input: tree 0-1,0-2,1-3,1-4; values=[1,2,3,4,5]; pathQuery(3,4) sum
Output: 11
Note: Path 3 → 1 → 4 with LCA 1. Node values are node3=4, node1=2, node4=5, so the sum is 4 + 2 + 5 = 11. See the dry run for how this splits into two chain ranges.

Example 3

Input: same tree; pathQuery(3, 2) sum
Output: 10
Note: Path 3 → 1 → 0 → 2, values 4 + 2 + 1 + 3 = 10. It crosses from node 3's light edge up to the heavy chain through the root.

Constraints

1 ≤ n ≤ 10⁵
Up to 10⁵ interleaved pathQuery and update calls
The tree is rooted and its shape does not change
Aggregate is associative (sum, max, min, gcd); values fit in 64-bit

Clarifying questions4First question: Are the queries on paths or subtrees?Explore questions

Q1.Are the queries on paths or subtrees?
Paths between two nodes. If they were subtree queries, an Euler tour with a Fenwick tree would be simpler and one log factor faster.
Q2.Are values on nodes or edges?
Nodes here. Edge-valued variants assign each edge to its deeper endpoint and exclude the LCA from the final segment — a common off-by-one to call out.
Q3.Does the tree change shape?
No. HLD assumes a fixed structure; the positions and chains are precomputed. Dynamic trees need link-cut trees.
Q4.How deep can recursion go?
Up to n on a chain. The two setup DFS passes should be iterative (explicit stack) so a 10⁵-deep tree does not overflow the call stack.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Heavy-light decomposition (HLD) makes path queries on a tree fast. Each node picks its child with the largest subtree as its 'heavy' child; the heavy edges link nodes into chains. Lay the chains out contiguously in an array (via DFS position) and back that array with a segment tree. Any root-to-node path crosses at most O(log n) chains, so a path query splits into O(log n) contiguous segment-tree ranges — giving O(log^2 n) per path query (O(log n) chains × O(log n) per range).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand why choosing the largest-subtree child bounds light edges at O(log n), and how that turns a path into O(log n) contiguous ranges a segment tree can answer.

Where candidates slip

Picking the heavy child by depth or degree instead of subtree size (losing the log bound), laying chains non-contiguously, or mishandling the final same-chain segment (forgetting to include the right endpoint or double-counting the LCA on edge-valued trees).

How to stand out

State the O(log n) light-edge bound from the halving argument, describe the two-DFS build crisply, and contrast HLD (paths, O(log^2 n)) with Euler tour (subtrees, O(log n)) and binary lifting (LCA only).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Walk the Path via the LCA	`O(n) per query, O(1) update`	`O(n)`	Say this first: it is the obvious correct method and shows why long paths force a smarter layout.	Read
2	Heavy-Light Decomposition + Segment Tree (Optimal)Optimal	`O(n) build, O(log² n) path query, O(log n) update`	`O(n)`	The answer they want for many path queries. 'Cut the tree into heavy chains, lay them contiguously, and a path becomes O(log n) segment-tree ranges.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Heavy edges form chains

How to read it:Solid edges are heavy (toward the largest-subtree child); a path crosses few light edges. head[] marks each chain's top.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Walk the Path via the LCA

TimeO(n) per query, O(1) updateSpaceO(n)

Say this first: it is the obvious correct method and shows why long paths force a smarter layout.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Find the LCA of u and v, then walk u up to the LCA and v up to the LCA, aggregating values along the way.

2Hint 2Explore hint

update(node, val) is one assignment — O(1).

3Hint 3Explore hint

A path can be the whole height of the tree, so a query is O(n). With many queries this is too slow — motivating a layout where a path is a few contiguous ranges.

A · Core idea

The direct method needs only parent pointers, depths, and per-node values.

Find the meeting point. Compute lca(u, v). The path from u to v is u → … → lca → … → v.

Walk and aggregate. Step u upward to the LCA, combining each node's value; do the same for v; include the LCA once. The combine is whatever the query asks (sum, max, …).

Why it is correct. Every node on the u-to-v path is on one of the two upward walks to their LCA, and the LCA is the single shared top.

Why it is too slow. A path can span the entire height of the tree — O(n) for a chain. Answering 10⁵ such queries is O(n·q). The remedy is to relabel nodes so that the path decomposes into a few contiguous ranges that a segment tree aggregates in logarithmic time — which is exactly what HLD provides.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree 0-1,0-2,1-3,1-4; values=[1,2,3,4,5]; pathQuery(3,2) sum

u side

3 (val 4) → 1 (val 2) → 0

Statepartial = 4 + 2 = 6

Final result10

C · Code with teaching comments

Reference implementation previewimport java.util.*; class NaivePath { private final List<List<Integer>> adj; private final int[] parent, depth;Explore the full code

solution.javaJava

Baseline — Walk the Path via the LCA — reference

3 teaching notes

1
import java.util.*;
2
 
3
class NaivePath {
4
    private final List<List<Integer>> adj;
5
    private final int[] parent, depth;
6
    private final long[] val;
7
 
8
    NaivePath(int n, int root, int[][] edges, long[] values) {
9
        adj = new ArrayList<>();
10
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
11
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
12
        parent = new int[n];
13
        depth = new int[n];
14
        val = values.clone();
15
        Deque<int[]> st = new ArrayDeque<>();
16
        boolean[] seen = new boolean[n];
17
        st.push(new int[]{root, root, 0});
18
        while (!st.isEmpty()) {
19
            int[] c = st.pop();
20
            if (seen[c[0]]) continue;
21
            seen[c[0]] = true; parent[c[0]] = c[1]; depth[c[0]] = c[2];
22
            for (int nx : adj.get(c[0])) if (!seen[nx]) st.push(new int[]{nx, c[0], c[2] + 1});
23
        }
24
    }
25
 
26
    void update(int node, long v) { val[node] = v; }
27
 
28
    long pathQuery(int u, int v) {
29
        long sum = 0;
30
        // Climb the deeper endpoint, aggregating, until depths match.
31
        while (depth[u] > depth[v]) { sum += val[u]; u = parent[u]; }
32
        while (depth[v] > depth[u]) { sum += val[v]; v = parent[v]; }
33
        // Climb both toward the LCA in lockstep — the O(n) bottleneck.
34
        while (u != v) { sum += val[u] + val[v]; u = parent[u]; v = parent[v]; }
35
        // Both walks stop at the LCA; add it a single time.
36
        sum += val[u];   // the LCA, counted once
37
        return sum;
38
    }
39
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.39 lines

D · Why it works and complexityO(n) per query, O(1) update timeO(n) spaceOpen the invariant and proofExplore the proof

The path-via-LCA walk is the conceptual baseline HLD accelerates: HLD keeps the same 'climb toward the LCA' motion but jumps a whole chain at a time (one segment-tree range) instead of one node at a time.

ComplexityO(n) per query, O(1) update time, O(n) space — Walking both halves of the path visits up to O(n) nodes (e.g. a chain). Updates are O(1). With q queries the cost is O(q·n).

E · Edge cases and pitfalls3Double-counting the LCA — add it exactly once after the loops.Explore edge cases

Pitfalls

Double-counting the LCA — add it exactly once after the loops.
Accepting O(n) per query — fine for one query, too slow for many.
Recursive setup DFS on a chain — stack overflow; use an explicit stack.

03.2

Approach 2 of 2 · Optimal

Heavy-Light Decomposition + Segment Tree (Optimal)

TimeO(n) build, O(log² n) path query, O(log n) updateSpaceO(n)

The answer they want for many path queries. 'Cut the tree into heavy chains, lay them contiguously, and a path becomes O(log n) segment-tree ranges.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First DFS: compute each node's subtree size and mark its heavy child (the child with the largest subtree). Heavy edges chain nodes together.

2Hint 2Explore hint

Second DFS: walk heavy children first so a chain's nodes get consecutive positions pos[node]; record head[node] = the top of the chain node belongs to. Build a segment tree over the base array indexed by pos.

3Hint 3Explore hint

Path query: while u and v are on different chains, take the segment-tree range for the deeper head's chain, then jump to parent[head] of that chain; once on the same chain, combine the final in-chain range. Each jump crosses one light edge, and there are at most O(log n) of those.

A · Core idea

Heavy-light decomposition relabels the tree so that arbitrary paths become a few contiguous ranges, then lets a segment tree do the aggregation.

Step 1 — choose heavy edges (why subtree size). For each node, its heavy child is the child with the largest subtree; the edge to it is a heavy edge, every other child edge is light. The reason for picking by subtree size is the crucial guarantee: when you descend a light edge from a node, the child's subtree is at most half the parent's (otherwise that child would have been the heavy one). Halving can happen at most log₂ n times along any downward path, so any root-to-node path crosses at most O(log n) light edges — equivalently, it passes through at most O(log n) heavy chains.

Step 2 — lay chains contiguously. A chain is a maximal run of heavy edges. In a second DFS we always recurse into the heavy child first, assigning positions pos[node] in visit order. This makes every chain occupy a contiguous block of positions, and we record head[node] = the topmost node of the chain containing node. We then build a segment tree over the base array where index pos[node] holds node's value.

Step 3 — answer a path query. To aggregate the path u … v, repeatedly look at the chain heads. While head[u] ≠ head[v], the two nodes are on different chains: pick whichever has the deeper head (say u), aggregate the contiguous range [pos[head[u]], pos[u]] from the segment tree (the whole portion of u's chain from its head down to u), then hop to the chain above by setting u = parent[head[u]]. Each hop crosses exactly one light edge, so this loop runs O(log n) times. When head[u] == head[v] the nodes are finally on the same chain; aggregate the single range between them ([pos[deeper], pos[shallower]]) and combine. The deeper-head node is implicitly the LCA's chain.

Why O(log² n). O(log n) chains, each costing an O(log n) segment-tree range query → O(log² n). Updates touch one position, so they are a plain O(log n) segment-tree update.

Node vs edge values. With values on nodes, include the LCA's position in the final same-chain range. With values on edges, store each edge's value at its deeper endpoint and exclude the LCA from that last range (pos[lca] + 1 instead of pos[lca]) so the edge above the LCA is not wrongly added — the standard HLD off-by-one.

How it relates to other tools. The Euler tour makes subtrees contiguous; HLD makes paths (in pieces) contiguous. Binary lifting answers LCA alone. HLD is the heavyweight when you need aggregates along paths under updates.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree 0-1,0-2,1-3,1-4; values=[1,2,3,4,5]; pathQuery(3,4) sum

Interactive diagram

Path 3 to 4 as two chain ranges

heads

Active call / nodeSupporting contextReturned stateNot active

Node 4 is a light child of 1 (its own chain); the rest of the path lives in the chain {0,1,3}. Two segment-tree ranges total.

Final result11

C · Code with teaching comments

solution.javaJava

Heavy-Light Decomposition + Segment Tree (Optimal) — optimal

6 teaching notes

1
import java.util.*;
2
 
3
class HLD {
4
    private final int n;
5
    private final List<List<Integer>> adj;
6
    private final int[] parent, depth, heavy, size, head, pos;
7
    private final long[] baseVal;     // value at each pos
8
    private final long[] seg;         // segment tree over baseVal (sum)
9
    private int timer = 0;
10
 
11
    HLD(int n, int root, int[][] edges, long[] values) {
12
        this.n = n;
13
        adj = new ArrayList<>();
14
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
15
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
16
        parent = new int[n]; depth = new int[n]; heavy = new int[n];
17
        size = new int[n]; head = new int[n]; pos = new int[n];
18
        baseVal = new long[n]; seg = new long[4 * n];
19
        Arrays.fill(heavy, -1);
20
 
21
        dfsSize(root);
22
        decompose(root, root);
23
        for (int v = 0; v < n; v++) baseVal[pos[v]] = values[v];
24
        build(1, 0, n - 1);
25
    }
26
 
27
    // DFS 1: subtree sizes + heavy child (iterative post-order).
28
    private void dfsSize(int root) {
29
        Deque<Integer> st = new ArrayDeque<>();
30
        int[] order = new int[n]; int idx = 0;
31
        boolean[] seen = new boolean[n];
32
        st.push(root); parent[root] = root; seen[root] = true;
33
        while (!st.isEmpty()) {
34
            int node = st.pop(); order[idx++] = node;
35
            for (int nx : adj.get(node)) if (!seen[nx]) {
36
                seen[nx] = true; parent[nx] = node; depth[nx] = depth[node] + 1; st.push(nx);
37
            }
38
        }
39
        for (int i = n - 1; i >= 0; i--) {   // children before parents
40
            int node = order[i];
41
            size[node] = 1;
42
            int best = -1, bestSize = 0;
43
            for (int c : adj.get(node)) if (c != parent[node]) {
44
                size[node] += size[c];
45
                // Heavy child = largest subtree — the choice that bounds light edges at
46
                // O(log n).
47
                if (size[c] > bestSize) { bestSize = size[c]; best = c; }
48
            }
49
            heavy[node] = best;
50
        }
51
    }
52
 
53
    // DFS 2: assign pos along chains, heavy child first (iterative).
54
    private void decompose(int root, int h) {
55
        Deque<int[]> st = new ArrayDeque<>();   // {node, chainHead}
56
        st.push(new int[]{root, h});
57
        while (!st.isEmpty()) {
58
            int[] top = st.pop();
59
            int node = top[0], chainHead = top[1];
60
            // Record the top of node's chain so path queries know where each chain
61
            // begins.
62
            head[node] = chainHead;
63
            pos[node] = timer++;
64
            // Push light children first so the heavy child is processed next (LIFO).
65
            for (int c : adj.get(node)) {
66
                if (c != parent[node] && c != heavy[node]) st.push(new int[]{c, c});
67
            }
68
            // Push the heavy child last so it is popped first, giving the chain
69
            // consecutive positions.
70
            if (heavy[node] != -1) st.push(new int[]{heavy[node], chainHead});
71
        }
72
    }
73
 
74
    private void build(int node, int lo, int hi) {
75
        if (lo == hi) { seg[node] = baseVal[lo]; return; }
76
        int mid = (lo + hi) >>> 1;
77
        build(2 * node, lo, mid); build(2 * node + 1, mid + 1, hi);
78
        seg[node] = seg[2 * node] + seg[2 * node + 1];
79
    }
80
 
81
    private void segUpdate(int node, int lo, int hi, int i, long v) {
82
        if (lo == hi) { seg[node] = v; return; }
83
        int mid = (lo + hi) >>> 1;
84
        if (i <= mid) segUpdate(2 * node, lo, mid, i, v);
85
        else segUpdate(2 * node + 1, mid + 1, hi, i, v);
86
        seg[node] = seg[2 * node] + seg[2 * node + 1];
87
    }
88
 
89
    private long segQuery(int node, int lo, int hi, int l, int r) {
90
        if (r < lo || hi < l) return 0;
91
        if (l <= lo && hi <= r) return seg[node];
92
        int mid = (lo + hi) >>> 1;
93
        return segQuery(2 * node, lo, mid, l, r) + segQuery(2 * node + 1, mid + 1, hi, l, r);
94
    }
95
 
96
    void update(int node, long v) {
97
        segUpdate(1, 0, n - 1, pos[node], v);
98
    }
99
 
100
    long pathQuery(int u, int v) {
101
        long res = 0;
102
        while (head[u] != head[v]) {                 // O(log n) chain hops
103
            if (depth[head[u]] < depth[head[v]]) { int t = u; u = v; v = t; }
104
            // One contiguous chain segment per hop — the heart of HLD.
105
            res += segQuery(1, 0, n - 1, pos[head[u]], pos[u]);
106
            u = parent[head[u]];
107
        }
108
        if (depth[u] > depth[v]) { int t = u; u = v; v = t; }
109
        res += segQuery(1, 0, n - 1, pos[u], pos[v]);  // final same-chain range
110
        return res;
111
    }
112
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.112 lines

D · Why it works and complexityO(n) build, O(log² n) path query, O(log n) update timeO(n) spaceOpen the invariant and proofExplore the proof

The entire power comes from one combinatorial fact: choosing the largest-subtree child as heavy forces light edges to be rare (≤ log n on any path). Rarity of light edges is what bounds the number of contiguous ranges a path decomposes into — and contiguous ranges are exactly what segment trees love. HLD is 'make the expensive thing (changing chains) rare, then reuse array structures'.

ComplexityO(n) build, O(log² n) path query, O(log n) update time, O(n) space — Both build DFS passes are O(n); building the segment tree is O(n). A path query crosses O(log n) chains (the light-edge bound), and each chain contributes one segment-tree range query costing O(log n) → O(log² n) per path query. A point update is one segment-tree update → O(log n).

E · Edge cases and pitfalls7pathQuery(node, node) — Same chain immediately; the final range is [pos[node], pos[node]] → the node's own value.Explore edge cases

Edge cases handled

pathQuery(node, node)Same chain immediately; the final range is [pos[node], pos[node]] → the node's own value.
straight chain treeEverything is one heavy chain; any path is a single contiguous range — HLD degenerates to a plain segment-tree range query.
edge-valued variantStore edge values at the deeper endpoint and use pos[lca] + 1 for the final range so the edge above the LCA is excluded.

Pitfalls

Choosing the heavy child by depth or degree instead of subtree size — loses the O(log n) light-edge bound.
Not visiting the heavy child first in DFS 2 — chains stop being contiguous and ranges break.
Double-counting or omitting the LCA in the final same-chain range (especially for edge values).
Recursive setup on a deep chain — stack overflow; build the two DFS passes iteratively.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class HLD { private final int n; private final List<List<Integer>> adj;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class HLD {
    private final int n;
    private final List<List<Integer>> adj;
    private final int[] parent, depth, heavy, size, head, pos;
    private final long[] baseVal;     // value at each pos
    private final long[] seg;         // segment tree over baseVal (sum)
    private int timer = 0;

HLD(int n, int root, int[][] edges, long[] values) {
        this.n = n;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        parent = new int[n]; depth = new int[n]; heavy = new int[n];
        size = new int[n]; head = new int[n]; pos = new int[n];
        baseVal = new long[n]; seg = new long[4 * n];
        Arrays.fill(heavy, -1);

dfsSize(root);
        decompose(root, root);
        for (int v = 0; v < n; v++) baseVal[pos[v]] = values[v];
        build(1, 0, n - 1);
    }

// DFS 1: subtree sizes + heavy child (iterative post-order).
    private void dfsSize(int root) {
        Deque<Integer> st = new ArrayDeque<>();
        int[] order = new int[n]; int idx = 0;
        boolean[] seen = new boolean[n];
        st.push(root); parent[root] = root; seen[root] = true;
        while (!st.isEmpty()) {
            int node = st.pop(); order[idx++] = node;
            for (int nx : adj.get(node)) if (!seen[nx]) {
                seen[nx] = true; parent[nx] = node; depth[nx] = depth[node] + 1; st.push(nx);
            }
        }
        for (int i = n - 1; i >= 0; i--) {   // children before parents
            int node = order[i];
            size[node] = 1;
            int best = -1, bestSize = 0;
            for (int c : adj.get(node)) if (c != parent[node]) {
                size[node] += size[c];
                if (size[c] > bestSize) { bestSize = size[c]; best = c; }
            }
            heavy[node] = best;
        }
    }

// DFS 2: assign pos along chains, heavy child first (iterative).
    private void decompose(int root, int h) {
        Deque<int[]> st = new ArrayDeque<>();   // {node, chainHead}
        st.push(new int[]{root, h});
        while (!st.isEmpty()) {
            int[] top = st.pop();
            int node = top[0], chainHead = top[1];
            head[node] = chainHead;
            pos[node] = timer++;
            // Push light children first so the heavy child is processed next (LIFO).
            for (int c : adj.get(node)) {
                if (c != parent[node] && c != heavy[node]) st.push(new int[]{c, c});
            }
            if (heavy[node] != -1) st.push(new int[]{heavy[node], chainHead});
        }
    }

private void build(int node, int lo, int hi) {
        if (lo == hi) { seg[node] = baseVal[lo]; return; }
        int mid = (lo + hi) >>> 1;
        build(2 * node, lo, mid); build(2 * node + 1, mid + 1, hi);
        seg[node] = seg[2 * node] + seg[2 * node + 1];
    }

private void segUpdate(int node, int lo, int hi, int i, long v) {
        if (lo == hi) { seg[node] = v; return; }
        int mid = (lo + hi) >>> 1;
        if (i <= mid) segUpdate(2 * node, lo, mid, i, v);
        else segUpdate(2 * node + 1, mid + 1, hi, i, v);
        seg[node] = seg[2 * node] + seg[2 * node + 1];
    }

private long segQuery(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return seg[node];
        int mid = (lo + hi) >>> 1;
        return segQuery(2 * node, lo, mid, l, r) + segQuery(2 * node + 1, mid + 1, hi, l, r);
    }

void update(int node, long v) {
        segUpdate(1, 0, n - 1, pos[node], v);
    }

long pathQuery(int u, int v) {
        long res = 0;
        while (head[u] != head[v]) {                 // O(log n) chain hops
            if (depth[head[u]] < depth[head[v]]) { int t = u; u = v; v = t; }
            res += segQuery(1, 0, n - 1, pos[head[u]], pos[u]);
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) { int t = u; u = v; v = t; }
        res += segQuery(1, 0, n - 1, pos[u], pos[v]);  // final same-chain range
        return res;
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong heavy-child rule

The O(log n) bound on light edges holds ONLY because the heavy child has the largest subtree, forcing every light edge to at least halve the remaining subtree. Picking by depth or first-child breaks the guarantee and paths can touch O(n) chains.

Explore the code comparison

Don't write this

self.heavy[node] = self.adj[node][0]   # arbitrary first child

Write this instead

best, best_size = -1, 0
for c in self.adj[node]:
    if c != self.parent[node] and self.size[c] > best_size:
        best_size, best = self.size[c], c
self.heavy[node] = best

Heavy child not visited first

Contiguous chains require the heavy child to receive the next consecutive position. If light children are positioned in between, a chain's nodes are scattered and a single segment-tree range no longer covers the chain.

Explore the code comparison

Don't write this

for (int c : adj.get(node)) {
    if (c != parent[node]) st.push(new int[]{c, c});  // heavy gets a new head too
}

Write this instead

for (int c : adj.get(node))
    if (c != parent[node] && c != heavy[node]) st.push(new int[]{c, c});
if (heavy[node] != -1) st.push(new int[]{heavy[node], head[node]}); // same chain, popped first

LCA handling in the final segment

For node values the LCA must be counted once — include pos[lca]. For edge values it must be excluded — use pos[lca] + 1 — or you add the edge above the LCA that is not on the path.

Explore the code comparison

Don't write this

# edge-valued tree, but including the LCA position:
res += self._seg_query(1, 0, self.n - 1, self.pos[u], self.pos[v])

Write this instead

# edge-valued tree: skip the LCA's own position
res += self._seg_query(1, 0, self.n - 1, self.pos[u] + 1, self.pos[v])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Heavy child = biggest subtree; chains laid contiguously; path = O(log n) chain ranges

Code pattern to memorize

heavy[node] = child with max subtree size
# DFS 1: subtree sizes + heavy child
# DFS 2: assign pos[node] along chains; head[node] = chain top
query(u, v):
  res = identity
  while head[u] != head[v]:
    if depth[head[u]] < depth[head[v]]: swap(u, v)
    res = combine(res, seg.query(pos[head[u]], pos[u]))
    u = parent[head[u]]
  # now same chain: combine the final in-chain range
  if depth[u] > depth[v]: swap(u, v)
  res = combine(res, seg.query(pos[u], pos[v]))

Rules to remember

1Heavy child = the child whose subtree is largest; ties broken arbitrarily. Every other child starts a new (light) chain.
2A light edge at least halves the subtree size going down, so any root-to-leaf path has at most log2 n light edges → O(log n) chains.
3Lay each chain contiguously in the base array so a chain segment is one segment-tree range.
4head[node] is the topmost node of node's chain; jump u = parent[head[u]] to hop to the next chain up.
5Climb the deeper head each step (compare depth[head[u]] vs depth[head[v]]) — this is implicitly walking toward the LCA.

Use this pattern when

Path queries/updates between two nodes (sum, max, add) on a static-shape tree
Mixing path aggregates with subtree aggregates (HLD orders nodes so both are ranges)
Repeated 'value on the path from u to v' questions where naive walking is too slow
When you already know segment trees and need to lift them to tree paths

Choose another pattern when

Only subtree queries, no paths → a plain Euler tour + Fenwick tree is simpler
Only LCA / distance, no aggregates → binary lifting is shorter
Tree changes shape between queries → link-cut trees handle dynamic trees instead
A single path query → just walk it in O(n); HLD's setup is not worth it

Interview takeaway

HLD is the bridge from 'range structure on an array' to 'range structure on tree paths'. By choosing heavy edges so light edges are rare (≤ log n on any path), it guarantees every path is a small union of contiguous chain ranges — letting a segment tree answer path queries in O(log^2 n).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternHeavy-light decomposition: mark the largest-subtree child of each node as heavy, lay the resulting chains contiguously, and back the array with a segment tree. Because light edges are at most O(log n) on any path, a path splits into O(log n) contiguous chain ranges, giving O(log² n) path queries and O(log n) updates. The standard tool for path aggregates with updates on a static-shape tree.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Path Update (add x to every node on a path)
Coming soon
Swap the segment tree for one with lazy propagation; decompose the path the same way and range-add each chain segment.
Subtree + Path Queries Together
Coming soon
HLD's pos ordering also makes each subtree contiguous (pos[node] .. pos[node] + size[node] − 1), so one segment tree serves both.
Euler Tour of a Tree
If you only need subtree queries, the simpler Euler tour + Fenwick tree is one log factor faster.
LCA with Binary Lifting
When you only need the LCA or distance (no aggregates), lifting is shorter than full HLD.

Same pattern

←

Fenwick Tree (Binary Indexed Tree)

Continue · Next problem

Segment Tree for Range Sum

hardTreesRarely asked

Heavy-Light Decomposition (Path Queries)

Trees & BST · 28 of 41 · 13 min

You are given a rooted tree with n nodes, each holding a value. Support many queries of the form:

1
**pathQuery(u, v)** — aggregate (e.g. sum or max) of the values on the path from u to v.
2
**update(node, val)** — change the value at a node.

The tree's shape is fixed. Use heavy-light decomposition with a segment tree so each path query runs in **O(log² n)** and each update in **O(log n)**.

In plain English

Examples

Example 1

Input: path tree 0-1-2-3-4 (a chain), values=[1,2,3,4,5]; pathQuery(0,4) sum
Output: 15
Note: A chain is a single heavy path, so the whole path is one contiguous segment-tree range: 1+2+3+4+5 = 15.

Example 2

Input: tree 0-1,0-2,1-3,1-4; values=[1,2,3,4,5]; pathQuery(3,4) sum
Output: 11
Note: Path 3 → 1 → 4 with LCA 1. Node values are node3=4, node1=2, node4=5, so the sum is 4 + 2 + 5 = 11. See the dry run for how this splits into two chain ranges.

Example 3

Input: same tree; pathQuery(3, 2) sum
Output: 10
Note: Path 3 → 1 → 0 → 2, values 4 + 2 + 1 + 3 = 10. It crosses from node 3's light edge up to the heavy chain through the root.

Constraints

1 ≤ n ≤ 10⁵
Up to 10⁵ interleaved pathQuery and update calls
The tree is rooted and its shape does not change
Aggregate is associative (sum, max, min, gcd); values fit in 64-bit

Clarifying questions4First question: Are the queries on paths or subtrees?Explore questions

Q1.Are the queries on paths or subtrees?
Paths between two nodes. If they were subtree queries, an Euler tour with a Fenwick tree would be simpler and one log factor faster.
Q2.Are values on nodes or edges?
Nodes here. Edge-valued variants assign each edge to its deeper endpoint and exclude the LCA from the final segment — a common off-by-one to call out.
Q3.Does the tree change shape?
No. HLD assumes a fixed structure; the positions and chains are precomputed. Dynamic trees need link-cut trees.
Q4.How deep can recursion go?
Up to n on a chain. The two setup DFS passes should be iterative (explicit stack) so a 10⁵-deep tree does not overflow the call stack.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand why choosing the largest-subtree child bounds light edges at O(log n), and how that turns a path into O(log n) contiguous ranges a segment tree can answer.

Where candidates slip

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Walk the Path via the LCA	`O(n) per query, O(1) update`	`O(n)`	Say this first: it is the obvious correct method and shows why long paths force a smarter layout.	Read
2	Heavy-Light Decomposition + Segment Tree (Optimal)Optimal	`O(n) build, O(log² n) path query, O(log n) update`	`O(n)`	The answer they want for many path queries. 'Cut the tree into heavy chains, lay them contiguously, and a path becomes O(log n) segment-tree ranges.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Heavy edges form chains

How to read it:Solid edges are heavy (toward the largest-subtree child); a path crosses few light edges. head[] marks each chain's top.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Walk the Path via the LCA

TimeO(n) per query, O(1) updateSpaceO(n)

Say this first: it is the obvious correct method and shows why long paths force a smarter layout.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Find the LCA of u and v, then walk u up to the LCA and v up to the LCA, aggregating values along the way.

2Hint 2Explore hint

update(node, val) is one assignment — O(1).

3Hint 3Explore hint

A path can be the whole height of the tree, so a query is O(n). With many queries this is too slow — motivating a layout where a path is a few contiguous ranges.

A · Core idea

The direct method needs only parent pointers, depths, and per-node values.

Find the meeting point. Compute lca(u, v). The path from u to v is u → … → lca → … → v.

Walk and aggregate. Step u upward to the LCA, combining each node's value; do the same for v; include the LCA once. The combine is whatever the query asks (sum, max, …).

Why it is correct. Every node on the u-to-v path is on one of the two upward walks to their LCA, and the LCA is the single shared top.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree 0-1,0-2,1-3,1-4; values=[1,2,3,4,5]; pathQuery(3,2) sum

u side

3 (val 4) → 1 (val 2) → 0

Statepartial = 4 + 2 = 6

Final result10

C · Code with teaching comments

Reference implementation previewimport java.util.*; class NaivePath { private final List<List<Integer>> adj; private final int[] parent, depth;Explore the full code

solution.javaJava

Baseline — Walk the Path via the LCA — reference

3 teaching notes

1
import java.util.*;
2
 
3
class NaivePath {
4
    private final List<List<Integer>> adj;
5
    private final int[] parent, depth;
6
    private final long[] val;
7
 
8
    NaivePath(int n, int root, int[][] edges, long[] values) {
9
        adj = new ArrayList<>();
10
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
11
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
12
        parent = new int[n];
13
        depth = new int[n];
14
        val = values.clone();
15
        Deque<int[]> st = new ArrayDeque<>();
16
        boolean[] seen = new boolean[n];
17
        st.push(new int[]{root, root, 0});
18
        while (!st.isEmpty()) {
19
            int[] c = st.pop();
20
            if (seen[c[0]]) continue;
21
            seen[c[0]] = true; parent[c[0]] = c[1]; depth[c[0]] = c[2];
22
            for (int nx : adj.get(c[0])) if (!seen[nx]) st.push(new int[]{nx, c[0], c[2] + 1});
23
        }
24
    }
25
 
26
    void update(int node, long v) { val[node] = v; }
27
 
28
    long pathQuery(int u, int v) {
29
        long sum = 0;
30
        // Climb the deeper endpoint, aggregating, until depths match.
31
        while (depth[u] > depth[v]) { sum += val[u]; u = parent[u]; }
32
        while (depth[v] > depth[u]) { sum += val[v]; v = parent[v]; }
33
        // Climb both toward the LCA in lockstep — the O(n) bottleneck.
34
        while (u != v) { sum += val[u] + val[v]; u = parent[u]; v = parent[v]; }
35
        // Both walks stop at the LCA; add it a single time.
36
        sum += val[u];   // the LCA, counted once
37
        return sum;
38
    }
39
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.39 lines

D · Why it works and complexityO(n) per query, O(1) update timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) per query, O(1) update time, O(n) space — Walking both halves of the path visits up to O(n) nodes (e.g. a chain). Updates are O(1). With q queries the cost is O(q·n).

E · Edge cases and pitfalls3Double-counting the LCA — add it exactly once after the loops.Explore edge cases

Pitfalls

Double-counting the LCA — add it exactly once after the loops.
Accepting O(n) per query — fine for one query, too slow for many.
Recursive setup DFS on a chain — stack overflow; use an explicit stack.

03.2

Approach 2 of 2 · Optimal

Heavy-Light Decomposition + Segment Tree (Optimal)

TimeO(n) build, O(log² n) path query, O(log n) updateSpaceO(n)

The answer they want for many path queries. 'Cut the tree into heavy chains, lay them contiguously, and a path becomes O(log n) segment-tree ranges.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First DFS: compute each node's subtree size and mark its heavy child (the child with the largest subtree). Heavy edges chain nodes together.

2Hint 2Explore hint

3Hint 3Explore hint

A · Core idea

Heavy-light decomposition relabels the tree so that arbitrary paths become a few contiguous ranges, then lets a segment tree do the aggregation.

Why O(log² n). O(log n) chains, each costing an O(log n) segment-tree range query → O(log² n). Updates touch one position, so they are a plain O(log n) segment-tree update.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree 0-1,0-2,1-3,1-4; values=[1,2,3,4,5]; pathQuery(3,4) sum

Interactive diagram

Path 3 to 4 as two chain ranges

heads

Active call / nodeSupporting contextReturned stateNot active

Node 4 is a light child of 1 (its own chain); the rest of the path lives in the chain {0,1,3}. Two segment-tree ranges total.

Final result11

C · Code with teaching comments

solution.javaJava

Heavy-Light Decomposition + Segment Tree (Optimal) — optimal

6 teaching notes

1
import java.util.*;
2
 
3
class HLD {
4
    private final int n;
5
    private final List<List<Integer>> adj;
6
    private final int[] parent, depth, heavy, size, head, pos;
7
    private final long[] baseVal;     // value at each pos
8
    private final long[] seg;         // segment tree over baseVal (sum)
9
    private int timer = 0;
10
 
11
    HLD(int n, int root, int[][] edges, long[] values) {
12
        this.n = n;
13
        adj = new ArrayList<>();
14
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
15
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
16
        parent = new int[n]; depth = new int[n]; heavy = new int[n];
17
        size = new int[n]; head = new int[n]; pos = new int[n];
18
        baseVal = new long[n]; seg = new long[4 * n];
19
        Arrays.fill(heavy, -1);
20
 
21
        dfsSize(root);
22
        decompose(root, root);
23
        for (int v = 0; v < n; v++) baseVal[pos[v]] = values[v];
24
        build(1, 0, n - 1);
25
    }
26
 
27
    // DFS 1: subtree sizes + heavy child (iterative post-order).
28
    private void dfsSize(int root) {
29
        Deque<Integer> st = new ArrayDeque<>();
30
        int[] order = new int[n]; int idx = 0;
31
        boolean[] seen = new boolean[n];
32
        st.push(root); parent[root] = root; seen[root] = true;
33
        while (!st.isEmpty()) {
34
            int node = st.pop(); order[idx++] = node;
35
            for (int nx : adj.get(node)) if (!seen[nx]) {
36
                seen[nx] = true; parent[nx] = node; depth[nx] = depth[node] + 1; st.push(nx);
37
            }
38
        }
39
        for (int i = n - 1; i >= 0; i--) {   // children before parents
40
            int node = order[i];
41
            size[node] = 1;
42
            int best = -1, bestSize = 0;
43
            for (int c : adj.get(node)) if (c != parent[node]) {
44
                size[node] += size[c];
45
                // Heavy child = largest subtree — the choice that bounds light edges at
46
                // O(log n).
47
                if (size[c] > bestSize) { bestSize = size[c]; best = c; }
48
            }
49
            heavy[node] = best;
50
        }
51
    }
52
 
53
    // DFS 2: assign pos along chains, heavy child first (iterative).
54
    private void decompose(int root, int h) {
55
        Deque<int[]> st = new ArrayDeque<>();   // {node, chainHead}
56
        st.push(new int[]{root, h});
57
        while (!st.isEmpty()) {
58
            int[] top = st.pop();
59
            int node = top[0], chainHead = top[1];
60
            // Record the top of node's chain so path queries know where each chain
61
            // begins.
62
            head[node] = chainHead;
63
            pos[node] = timer++;
64
            // Push light children first so the heavy child is processed next (LIFO).
65
            for (int c : adj.get(node)) {
66
                if (c != parent[node] && c != heavy[node]) st.push(new int[]{c, c});
67
            }
68
            // Push the heavy child last so it is popped first, giving the chain
69
            // consecutive positions.
70
            if (heavy[node] != -1) st.push(new int[]{heavy[node], chainHead});
71
        }
72
    }
73
 
74
    private void build(int node, int lo, int hi) {
75
        if (lo == hi) { seg[node] = baseVal[lo]; return; }
76
        int mid = (lo + hi) >>> 1;
77
        build(2 * node, lo, mid); build(2 * node + 1, mid + 1, hi);
78
        seg[node] = seg[2 * node] + seg[2 * node + 1];
79
    }
80
 
81
    private void segUpdate(int node, int lo, int hi, int i, long v) {
82
        if (lo == hi) { seg[node] = v; return; }
83
        int mid = (lo + hi) >>> 1;
84
        if (i <= mid) segUpdate(2 * node, lo, mid, i, v);
85
        else segUpdate(2 * node + 1, mid + 1, hi, i, v);
86
        seg[node] = seg[2 * node] + seg[2 * node + 1];
87
    }
88
 
89
    private long segQuery(int node, int lo, int hi, int l, int r) {
90
        if (r < lo || hi < l) return 0;
91
        if (l <= lo && hi <= r) return seg[node];
92
        int mid = (lo + hi) >>> 1;
93
        return segQuery(2 * node, lo, mid, l, r) + segQuery(2 * node + 1, mid + 1, hi, l, r);
94
    }
95
 
96
    void update(int node, long v) {
97
        segUpdate(1, 0, n - 1, pos[node], v);
98
    }
99
 
100
    long pathQuery(int u, int v) {
101
        long res = 0;
102
        while (head[u] != head[v]) {                 // O(log n) chain hops
103
            if (depth[head[u]] < depth[head[v]]) { int t = u; u = v; v = t; }
104
            // One contiguous chain segment per hop — the heart of HLD.
105
            res += segQuery(1, 0, n - 1, pos[head[u]], pos[u]);
106
            u = parent[head[u]];
107
        }
108
        if (depth[u] > depth[v]) { int t = u; u = v; v = t; }
109
        res += segQuery(1, 0, n - 1, pos[u], pos[v]);  // final same-chain range
110
        return res;
111
    }
112
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.112 lines

D · Why it works and complexityO(n) build, O(log² n) path query, O(log n) update timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7pathQuery(node, node) — Same chain immediately; the final range is [pos[node], pos[node]] → the node's own value.Explore edge cases

Edge cases handled

pathQuery(node, node)Same chain immediately; the final range is [pos[node], pos[node]] → the node's own value.
straight chain treeEverything is one heavy chain; any path is a single contiguous range — HLD degenerates to a plain segment-tree range query.
edge-valued variantStore edge values at the deeper endpoint and use pos[lca] + 1 for the final range so the edge above the LCA is excluded.

Pitfalls

Choosing the heavy child by depth or degree instead of subtree size — loses the O(log n) light-edge bound.
Not visiting the heavy child first in DFS 2 — chains stop being contiguous and ranges break.
Double-counting or omitting the LCA in the final same-chain range (especially for edge values).
Recursive setup on a deep chain — stack overflow; build the two DFS passes iteratively.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class HLD { private final int n; private final List<List<Integer>> adj;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

dfsSize(root);
        decompose(root, root);
        for (int v = 0; v < n; v++) baseVal[pos[v]] = values[v];
        build(1, 0, n - 1);
    }

void update(int node, long v) {
        segUpdate(1, 0, n - 1, pos[node], v);
    }

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong heavy-child rule

Explore the code comparison

Don't write this

self.heavy[node] = self.adj[node][0]   # arbitrary first child

Write this instead

best, best_size = -1, 0
for c in self.adj[node]:
    if c != self.parent[node] and self.size[c] > best_size:
        best_size, best = self.size[c], c
self.heavy[node] = best

Heavy child not visited first

Explore the code comparison

Don't write this

for (int c : adj.get(node)) {
    if (c != parent[node]) st.push(new int[]{c, c});  // heavy gets a new head too
}

Write this instead

for (int c : adj.get(node))
    if (c != parent[node] && c != heavy[node]) st.push(new int[]{c, c});
if (heavy[node] != -1) st.push(new int[]{heavy[node], head[node]}); // same chain, popped first

LCA handling in the final segment

For node values the LCA must be counted once — include pos[lca]. For edge values it must be excluded — use pos[lca] + 1 — or you add the edge above the LCA that is not on the path.

Explore the code comparison

Don't write this

# edge-valued tree, but including the LCA position:
res += self._seg_query(1, 0, self.n - 1, self.pos[u], self.pos[v])

Write this instead

# edge-valued tree: skip the LCA's own position
res += self._seg_query(1, 0, self.n - 1, self.pos[u] + 1, self.pos[v])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Heavy child = biggest subtree; chains laid contiguously; path = O(log n) chain ranges

Code pattern to memorize

heavy[node] = child with max subtree size
# DFS 1: subtree sizes + heavy child
# DFS 2: assign pos[node] along chains; head[node] = chain top
query(u, v):
  res = identity
  while head[u] != head[v]:
    if depth[head[u]] < depth[head[v]]: swap(u, v)
    res = combine(res, seg.query(pos[head[u]], pos[u]))
    u = parent[head[u]]
  # now same chain: combine the final in-chain range
  if depth[u] > depth[v]: swap(u, v)
  res = combine(res, seg.query(pos[u], pos[v]))

Rules to remember

1Heavy child = the child whose subtree is largest; ties broken arbitrarily. Every other child starts a new (light) chain.
2A light edge at least halves the subtree size going down, so any root-to-leaf path has at most log2 n light edges → O(log n) chains.
3Lay each chain contiguously in the base array so a chain segment is one segment-tree range.
4head[node] is the topmost node of node's chain; jump u = parent[head[u]] to hop to the next chain up.
5Climb the deeper head each step (compare depth[head[u]] vs depth[head[v]]) — this is implicitly walking toward the LCA.

Use this pattern when

Path queries/updates between two nodes (sum, max, add) on a static-shape tree
Mixing path aggregates with subtree aggregates (HLD orders nodes so both are ranges)
Repeated 'value on the path from u to v' questions where naive walking is too slow
When you already know segment trees and need to lift them to tree paths

Choose another pattern when

Only subtree queries, no paths → a plain Euler tour + Fenwick tree is simpler
Only LCA / distance, no aggregates → binary lifting is shorter
Tree changes shape between queries → link-cut trees handle dynamic trees instead
A single path query → just walk it in O(n); HLD's setup is not worth it

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Path Update (add x to every node on a path)
Coming soon
Swap the segment tree for one with lazy propagation; decompose the path the same way and range-add each chain segment.
Subtree + Path Queries Together
Coming soon
HLD's pos ordering also makes each subtree contiguous (pos[node] .. pos[node] + size[node] − 1), so one segment tree serves both.
Euler Tour of a Tree
If you only need subtree queries, the simpler Euler tour + Fenwick tree is one log factor faster.
LCA with Binary Lifting
When you only need the LCA or distance (no aggregates), lifting is shorter than full HLD.

Same pattern

←

Fenwick Tree (Binary Indexed Tree)

Continue · Next problem

Segment Tree for Range Sum