Algorithm Deep Dive: Heavy-Light Decomposition (HLD)

Why Linearize a Tree?

Range data structures are powerful because an array interval is easy to describe. A tree path is not: it bends upward toward a lowest common ancestor and then downward through another branch. Heavy-Light Decomposition (HLD) is the adapter between those worlds.

HLD does not answer sums, maxima, or updates by itself. It assigns each vertex a position so that every root-to-leaf route changes chains only logarithmically many times. A segment tree, Fenwick tree, sparse table, or another one-dimensional structure then handles the resulting intervals.

The three-layer mental model

TreeThe original hierarchy defines parent, depth, subtree size, and paths.

HLDThe decomposition converts each path into $O(\log N)$ contiguous array intervals.

Range DSThe chosen data structure aggregates or updates each interval.

Heavy vs. Light Edges

Root the tree and compute $size[u]$, the number of vertices in $u$'s subtree. For every non-leaf $u$, choose one child with maximum subtree size as heavy[u]; ties may be broken arbitrarily.

The edge from $u$ to that chosen child is heavy.
Every other child edge is light.
Maximal runs of heavy edges form vertex-disjoint chains.

The chosen heavy child does not need more than half of $u$'s subtree. The half-size guarantee applies to every light child: if a non-chosen child had more than half, the chosen maximum child would be at least as large and the two could not both fit beneath $u$.

Heavy edges follow the largest remaining subtree. A light edge starts a new chain—and certifies a multiplicative drop in subtree size.

The name is about the complement

The proof does not require the heavy child itself to contain more than half the subtree. It requires every light child to contain at most half. Choosing a largest child heavy guarantees exactly that.

Working Principle and Construction

Root and validate the tree.Record parent[u], depth[u], and a traversal order.

Compute subtree sizes bottom-up.Process the traversal in reverse. Set size[u] = 1 + Σ size[child] and remember a largest child as heavy[u].

Walk heavy children first.Give a heavy child the same chain head as its parent. Every light child becomes the head of a new chain.

Assign array positions.Increase a global counter as vertices are visited. Heavy-first order keeps every chain—and every subtree—contiguous.

Build a range structure.Store the value of vertex $u$ at base[pos[u]], then build the segment tree or Fenwick tree over base.

Chains Become Array Ranges

The decomposition is useful only because it controls the layout. Every heavy chain occupies one consecutive array interval. With the usual heavy-first preorder, every subtree is also consecutive.

HLD changes representation, not the underlying tree. The base array groups chains, while heavy-first preorder simultaneously preserves subtree intervals.

`head[u]`

The topmost vertex of $u$'s current heavy chain. Equal heads mean two vertices occupy one continuous chain interval.

`pos[u]`

The index where $u$'s value lives in the base array. A chain slice becomes [pos[top], pos[bottom]].

`size[u]`

The number of vertices below $u$, including $u$. Its subtree interval is [pos[u], pos[u]+size[u]-1].

`parent[head[u]]`

The jump that leaves one chain. It crosses exactly one light edge and moves strictly toward the root.

Path Queries and Updates

Keep endpoints $u$ and $v$. While their chain heads differ, process the deeper head's entire suffix, then jump that endpoint above the head. When the heads match, process the final interval between the endpoints.

The loop always removes a suffix of the deeper chain. Each removal jumps across one light edge, so only logarithmically many intervals can be produced.

Compare chain heads, not endpoints.If depth[head[u]] < depth[head[v]], swap $u$ and $v$ so $u$ belongs to the deeper chain.

Consume one chain suffix.Aggregate the array range [pos[head[u]], pos[u]].

Cross one light edge.Set u = parent[head[u]] and repeat until both endpoints share a head.

Finish inside one chain.Order the endpoints by depth and aggregate [pos[u], pos[v]].

Vertex Values, Edge Values, and Operation Order

Vertex-valued path

Store value[u] at pos[u]. Include both ends of every processed interval. The final same-chain range includes the LCA exactly once.

The implementations below use this model with maximum as the aggregate.

Edge-valued path

Store edge $(parent[u],u)$ at the deeper endpoint pos[u]. Chain-jump intervals still include their heads, but the final same-chain interval begins at pos[ancestor]+1 to exclude the LCA's incoming edge.

Subtree interval

Heavy-first preorder makes every subtree contiguous: [pos[u], pos[u]+size[u]-1]. One range query answers a subtree aggregate in $O(\log N)$.

Non-commutative operations

Maximum and sum ignore interval order. Matrix products, strings, and function composition do not; preserve the $u\to LCA$ and $LCA\to v$ directions and reverse chain aggregates where necessary.

The classic off-by-one

For edge values, querying [pos[lca], pos[deeper]] accidentally includes the edge entering the LCA, which is not on the requested path. Use [pos[lca]+1, pos[deeper]] for the final chain segment.

Worked Query: Path 6 to 9

Using the decomposition in the SVGs, process the endpoint whose chain head is deeper. The exact order of the first two equal-depth choices may vary, but the resulting set of intervals is the same.

State	Deeper chain	Array interval	Jump
`u=6, v=9`	head 4	`[pos[4],pos[6]] = [5,6]`	`u=parent[4]=1`
`u=1, v=9`	head 9	`[pos[9],pos[9]] = [9,9]`	`v=parent[9]=2`
`u=1, v=2`	head 2	`[pos[2],pos[2]] = [7,7]`	`v=parent[2]=0`
`u=1, v=0`	same head 0	`[pos[0],pos[1]] = [0,1]`	finish

The queried vertices are ${6,4,9,2,0,1}$, precisely the simple path $6\to4\to1\to0\to2\to9$. Each of four segment-tree queries costs $O(\log N)$.

Why the Decomposition and Query Are Correct

Only logarithmically many light edges

If $(u,v)$ is light and $v$ is a child, then $size[v]\le (size[u]-1)/2 < size[u]/2$. After crossing $k$ light edges downward, the remaining subtree contains fewer than $N/2^k$ vertices. It cannot contain fewer than one, so $k<\log_2 N+1$.

A path $u\leftrightarrow v$ consists of two ancestor paths meeting at their LCA. Each half crosses $O(\log N)$ light edges; their sum is still $O(\log N)$. Therefore the path intersects only $O(\log N)$ heavy chains.

The query covers exactly the path

When the chain heads differ, the deeper head cannot be an ancestor of the other endpoint. The chain suffix from that head to its endpoint is therefore wholly part of the desired path. Removing it and jumping to the head's parent preserves the unprocessed remainder. Once the heads match, the unique remaining path is exactly the array interval between the two positions.

The shortest mental model: heavy edges keep long movement inside an array interval; light edges are the rare moments when a path query must start another interval.

HLD's guarantee comes from counting chain changes, not from making every chain long.

Complexity Analysis

Operation	HLD work	With segment tree	Notes
Preprocess decomposition	$O(N)$	$O(N)$	Parent/depth/order, sizes, heavy child, heads, and positions
Build range structure	—	$O(N)$	Over the linearized base array
Point update	One position	$O(\log N)$	Update `pos[u]`
Subtree query	One interval	$O(\log N)$	`[pos[u], pos[u]+size[u]-1]`
Path query	$O(\log N)$ intervals	$O(\log^2 N)$	Each interval costs $O(\log N)$
Path range update	$O(\log N)$ intervals	$O(\log^2 N)$	Requires lazy propagation for range updates

When can path queries become $O(\log N)$?

For some static or prefix-friendly aggregates, extra per-chain preprocessing can avoid a full segment-tree query for every chain. The standard general-purpose bound remains $O(\log^2 N)$, which is the safest expectation for dynamic point updates plus path queries.

Implementation

This vertex-valued implementation uses maximum as the aggregate. Both preprocessing passes and the segment tree are iterative, avoiding recursion limits on path-shaped trees. The constructor also checks that the input is one connected, acyclic tree.

NEG_INF = float("-inf")

class SegmentTree:
    def __init__(self, values):
        self.size = 1
        while self.size < len(values):
            self.size *= 2
        self.tree = [NEG_INF] * (2 * self.size)
        self.tree[self.size:self.size + len(values)] = values
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, index, value):
        i = self.size + index
        self.tree[i] = value
        i //= 2
        while i:
            self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])
            i //= 2

    def query(self, left, right):
        """Maximum on the inclusive interval [left, right]."""
        result = NEG_INF
        left += self.size
        right += self.size
        while left <= right:
            if left & 1:
                result = max(result, self.tree[left])
                left += 1
            if not (right & 1):
                result = max(result, self.tree[right])
                right -= 1
            left //= 2
            right //= 2
        return result


class HeavyLightDecomposition:
    def __init__(self, adj, values, root=0):
        self.n = len(adj)
        if self.n == 0 or len(values) != self.n or not 0 <= root < self.n:
            raise ValueError("need a non-empty tree, one value per vertex, and a valid root")

        self.parent = [-1] * self.n
        self.depth = [0] * self.n
        self.size = [1] * self.n
        self.heavy = [-1] * self.n
        self.head = [0] * self.n
        self.pos = [0] * self.n
        self.parent[root] = root
        order = [root]

        for u in order:
            for v in adj[u]:
                if not 0 <= v < self.n:
                    raise ValueError("neighbor index out of range")
                if v == u:
                    raise ValueError("input contains a self-loop")
                if v == self.parent[u]:
                    continue
                if self.parent[v] != -1:
                    raise ValueError("input contains a cycle")
                self.parent[v] = u
                self.depth[v] = self.depth[u] + 1
                order.append(v)

        if len(order) != self.n:
            raise ValueError("input tree is disconnected")

        for u in reversed(order):
            largest = 0
            for v in adj[u]:
                if self.parent[v] == u:
                    self.size[u] += self.size[v]
                    if self.size[v] > largest:
                        largest = self.size[v]
                        self.heavy[u] = v

        base = [0] * self.n
        next_pos = 0
        chain_starts = [(root, root)]
        while chain_starts:
            u, chain_head = chain_starts.pop()
            while u != -1:
                self.head[u] = chain_head
                self.pos[u] = next_pos
                base[next_pos] = values[u]
                next_pos += 1

                for v in adj[u]:
                    if self.parent[v] == u and v != self.heavy[u]:
                        chain_starts.append((v, v))
                u = self.heavy[u]

        self.seg = SegmentTree(base)

    def _check_vertex(self, u):
        if not 0 <= u < self.n:
            raise IndexError("vertex out of range")

    def update_vertex(self, u, value):
        self._check_vertex(u)
        self.seg.update(self.pos[u], value)

    def query_path(self, u, v):
        self._check_vertex(u)
        self._check_vertex(v)
        result = NEG_INF
        while self.head[u] != self.head[v]:
            if self.depth[self.head[u]] < self.depth[self.head[v]]:
                u, v = v, u
            result = max(result, self.seg.query(self.pos[self.head[u]], self.pos[u]))
            u = self.parent[self.head[u]]

        if self.depth[u] > self.depth[v]:
            u, v = v, u
        return max(result, self.seg.query(self.pos[u], self.pos[v]))

    def query_subtree(self, u):
        self._check_vertex(u)
        return self.seg.query(self.pos[u], self.pos[u] + self.size[u] - 1)


values = [10, 20, 30, 40, 50, 60]
adj = [[] for _ in values]
for u, v in [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)]:
    adj[u].append(v)
    adj[v].append(u)

hld = HeavyLightDecomposition(adj, values)
print("path max (3, 5):", hld.query_path(3, 5))  # 60
print("subtree max (1):", hld.query_subtree(1))   # 50
hld.update_vertex(3, 99)
print("after update:", hld.query_path(3, 5))      # 99

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <stdexcept>
#include <utility>

using namespace std;

class SegmentTree {
    int size;
    vector<long long> tree;
public:
    static constexpr long long NEG_INF = numeric_limits<long long>::lowest();

    explicit SegmentTree(const vector<long long>& values) : size(1) {
        while (size < static_cast<int>(values.size())) size *= 2;
        tree.assign(2 * size, NEG_INF);
        for (int i = 0; i < static_cast<int>(values.size()); ++i) {
            tree[size + i] = values[i];
        }
        for (int i = size - 1; i > 0; --i) {
            tree[i] = max(tree[2 * i], tree[2 * i + 1]);
        }
    }

    void update(int index, long long value) {
        int i = size + index;
        tree[i] = value;
        for (i /= 2; i > 0; i /= 2) {
            tree[i] = max(tree[2 * i], tree[2 * i + 1]);
        }
    }

    long long query(int left, int right) const {
        long long result = NEG_INF;
        left += size;
        right += size;
        while (left <= right) {
            if (left & 1) result = max(result, tree[left++]);
            if (!(right & 1)) result = max(result, tree[right--]);
            left /= 2;
            right /= 2;
        }
        return result;
    }
};

class HLD {
    int n;
    vector<int> parent, depth, subtreeSize, heavy, head, pos;
    SegmentTree seg;

    void checkVertex(int u) const {
        if (u < 0 || u >= n) throw out_of_range("vertex out of range");
    }

public:
    HLD(const vector<vector<int>>& adj, const vector<long long>& values, int root = 0)
        : n(static_cast<int>(adj.size())), seg(vector<long long>{0}) {
        if (n == 0 || static_cast<int>(values.size()) != n || root < 0 || root >= n) {
            throw invalid_argument("need a non-empty tree, one value per vertex, and a valid root");
        }

        parent.assign(n, -1);
        depth.assign(n, 0);
        subtreeSize.assign(n, 1);
        heavy.assign(n, -1);
        head.assign(n, 0);
        pos.assign(n, 0);
        parent[root] = root;
        vector<int> order{root};

        for (size_t i = 0; i < order.size(); ++i) {
            int u = order[i];
            for (int v : adj[u]) {
                checkVertex(v);
                if (v == u) throw invalid_argument("input contains a self-loop");
                if (v == parent[u]) continue;
                if (parent[v] != -1) throw invalid_argument("input contains a cycle");
                parent[v] = u;
                depth[v] = depth[u] + 1;
                order.push_back(v);
            }
        }
        if (static_cast<int>(order.size()) != n) {
            throw invalid_argument("input tree is disconnected");
        }

        for (auto it = order.rbegin(); it != order.rend(); ++it) {
            int u = *it, largest = 0;
            for (int v : adj[u]) {
                if (parent[v] == u) {
                    subtreeSize[u] += subtreeSize[v];
                    if (subtreeSize[v] > largest) {
                        largest = subtreeSize[v];
                        heavy[u] = v;
                    }
                }
            }
        }

        vector<long long> base(n);
        int nextPos = 0;
        vector<pair<int, int>> chainStarts{{root, root}};
        while (!chainStarts.empty()) {
            auto [u, chainHead] = chainStarts.back();
            chainStarts.pop_back();
            while (u != -1) {
                head[u] = chainHead;
                pos[u] = nextPos;
                base[nextPos++] = values[u];
                for (int v : adj[u]) {
                    if (parent[v] == u && v != heavy[u]) chainStarts.push_back({v, v});
                }
                u = heavy[u];
            }
        }
        seg = SegmentTree(base);
    }

    void updateVertex(int u, long long value) {
        checkVertex(u);
        seg.update(pos[u], value);
    }

    long long queryPath(int u, int v) const {
        checkVertex(u);
        checkVertex(v);
        long long result = SegmentTree::NEG_INF;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) swap(u, v);
            result = max(result, seg.query(pos[head[u]], pos[u]));
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        return max(result, seg.query(pos[u], pos[v]));
    }

    long long querySubtree(int u) const {
        checkVertex(u);
        return seg.query(pos[u], pos[u] + subtreeSize[u] - 1);
    }
};

int main() {
    vector<long long> values = {10, 20, 30, 40, 50, 60};
    vector<vector<int>> adj(values.size());
    vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}};
    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    HLD hld(adj, values);
    cout << "path max (3, 5): " << hld.queryPath(3, 5) << '\n'; // 60
    cout << "subtree max (1): " << hld.querySubtree(1) << '\n';  // 50
    hld.updateVertex(3, 99);
    cout << "after update: " << hld.queryPath(3, 5) << '\n';     // 99
    return 0;
}

import java.util.*;

public class HLD {
    static class SegmentTree {
        static final long NEG_INF = Long.MIN_VALUE;
        int size = 1;
        long[] tree;

        SegmentTree(long[] values) {
            while (size < values.length) size *= 2;
            tree = new long[2 * size];
            Arrays.fill(tree, NEG_INF);
            System.arraycopy(values, 0, tree, size, values.length);
            for (int i = size - 1; i > 0; i--) {
                tree[i] = Math.max(tree[2 * i], tree[2 * i + 1]);
            }
        }

        void update(int index, long value) {
            int i = size + index;
            tree[i] = value;
            for (i /= 2; i > 0; i /= 2) {
                tree[i] = Math.max(tree[2 * i], tree[2 * i + 1]);
            }
        }

        long query(int left, int right) {
            long result = NEG_INF;
            left += size;
            right += size;
            while (left <= right) {
                if ((left & 1) == 1) result = Math.max(result, tree[left++]);
                if ((right & 1) == 0) result = Math.max(result, tree[right--]);
                left /= 2;
                right /= 2;
            }
            return result;
        }
    }

    private final int n;
    private final int[] parent, depth, subtreeSize, heavy, head, pos;
    private final SegmentTree seg;

    public HLD(List<List<Integer>> adj, long[] values, int root) {
        n = adj.size();
        if (n == 0 || values.length != n || root < 0 || root >= n) {
            throw new IllegalArgumentException(
                "need a non-empty tree, one value per vertex, and a valid root"
            );
        }

        parent = new int[n]; Arrays.fill(parent, -1);
        depth = new int[n];
        subtreeSize = new int[n]; Arrays.fill(subtreeSize, 1);
        heavy = new int[n]; Arrays.fill(heavy, -1);
        head = new int[n];
        pos = new int[n];
        parent[root] = root;

        List<Integer> order = new ArrayList<>();
        order.add(root);
        for (int i = 0; i < order.size(); i++) {
            int u = order.get(i);
            for (int v : adj.get(u)) {
                checkVertex(v);
                if (v == u) throw new IllegalArgumentException("input contains a self-loop");
                if (v == parent[u]) continue;
                if (parent[v] != -1) {
                    throw new IllegalArgumentException("input contains a cycle");
                }
                parent[v] = u;
                depth[v] = depth[u] + 1;
                order.add(v);
            }
        }
        if (order.size() != n) throw new IllegalArgumentException("input tree is disconnected");

        for (int i = order.size() - 1; i >= 0; i--) {
            int u = order.get(i);
            int largest = 0;
            for (int v : adj.get(u)) {
                if (parent[v] == u) {
                    subtreeSize[u] += subtreeSize[v];
                    if (subtreeSize[v] > largest) {
                        largest = subtreeSize[v];
                        heavy[u] = v;
                    }
                }
            }
        }

        long[] base = new long[n];
        int nextPos = 0;
        Deque<int[]> chainStarts = new ArrayDeque<>();
        chainStarts.push(new int[]{root, root});
        while (!chainStarts.isEmpty()) {
            int[] start = chainStarts.pop();
            int u = start[0], chainHead = start[1];
            while (u != -1) {
                head[u] = chainHead;
                pos[u] = nextPos;
                base[nextPos++] = values[u];
                for (int v : adj.get(u)) {
                    if (parent[v] == u && v != heavy[u]) {
                        chainStarts.push(new int[]{v, v});
                    }
                }
                u = heavy[u];
            }
        }
        seg = new SegmentTree(base);
    }

    private void checkVertex(int u) {
        if (u < 0 || u >= n) throw new IndexOutOfBoundsException("vertex out of range");
    }

    public void updateVertex(int u, long value) {
        checkVertex(u);
        seg.update(pos[u], value);
    }

    public long queryPath(int u, int v) {
        checkVertex(u);
        checkVertex(v);
        long result = SegmentTree.NEG_INF;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) {
                int temp = u; u = v; v = temp;
            }
            result = Math.max(result, seg.query(pos[head[u]], pos[u]));
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) {
            int temp = u; u = v; v = temp;
        }
        return Math.max(result, seg.query(pos[u], pos[v]));
    }

    public long querySubtree(int u) {
        checkVertex(u);
        return seg.query(pos[u], pos[u] + subtreeSize[u] - 1);
    }

    public static void main(String[] args) {
        int n = 6;
        long[] values = {10, 20, 30, 40, 50, 60};
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}};
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        HLD hld = new HLD(adj, values, 0);
        System.out.println("path max (3, 5): " + hld.queryPath(3, 5)); // 60
        System.out.println("subtree max (1): " + hld.querySubtree(1));  // 50
        hld.updateVertex(3, 99);
        System.out.println("after update: " + hld.queryPath(3, 5));    // 99
    }
}

Real-World Applications

Rooted network backbones

When the topology is a fixed routing tree but capacities or health scores change, HLD can update one link or vertex and query the minimum, maximum, or sum along a route.

Hierarchy analytics

On a static organizational or directory tree, HLD supports aggregates along reporting or containment paths while individual scores or permissions change.

Game and dependency trees

Skill trees and fixed dependency hierarchies can ask for the strongest requirement, accumulated cost, or enabled count along the path between two states.

Algorithmic query engines

HLD is a common foundation when a problem mixes static tree topology with online point updates, subtree aggregates, and arbitrary path queries.

Exercises

Trace the decomposition

Recompute every subtree size in the first SVG. Verify the heavy choice at vertices 0, 1, 2, 3, 4, and 5.
Swap the tie choice at vertex 2 from child 7 to child 9. Write the new chains and base array; explain why correctness and complexity do not change.
List the chain intervals generated for paths $8\leftrightarrow7$ and $3\leftrightarrow6$.

A different valid decomposition can yield different intervals without changing the represented tree path.

Move from vertices to edges

Store each edge's weight at its deeper endpoint and implement queryPathEdges.
Test the empty edge path from a vertex to itself. Decide which identity value your aggregate should return.
Demonstrate the wrong result produced when the final interval includes pos[lca].

All chain-jump ranges keep their head; only the final same-chain range skips the ancestor vertex.

Extend the range operations

Replace maximum with sum. Identify the identity element and every line that must change.
Add lazy propagation for “add $x$ to every vertex on path $u\leftrightarrow v$.”
Challenge: support string concatenation along $u\to v$ while preserving direction through the LCA.

Limitations

Situation	Why HLD may be awkward	Consider instead
Only subtree queries	A normal Euler preorder already makes each subtree one interval.	Euler tour plus one Fenwick or segment tree
Only LCA queries	The range structure and chain loop are unnecessary overhead.	Binary lifting or Euler-tour RMQ
Edges are linked or cut	Parents, sizes, heavy choices, and positions become stale.	A dynamic-tree structure such as a link-cut tree
Non-commutative aggregate	Naively combining chain results loses path direction.	Store forward/reverse aggregates and join them carefully
Path-shaped tree with recursive DFS	The traversal can overflow the language call stack.	Iterative preprocessing, as implemented above
Very simple or small input	HLD's implementation and constant factors may dominate.	Direct climbing or straightforward per-query traversal

Static topology, dynamic data

Standard HLD is designed for a fixed tree whose vertex or edge values change. Updating values is cheap; changing which vertices are connected invalidates the decomposition.

Cookie Consent

Heavy-Light Decomposition (HLD)

Contents

Why Linearize a Tree?

The three-layer mental model

Heavy vs. Light Edges

The name is about the complement

Working Principle and Construction

Chains Become Array Ranges

`head[u]`

`pos[u]`

`size[u]`

`parent[head[u]]`

Path Queries and Updates

Vertex Values, Edge Values, and Operation Order

Vertex-valued path

Edge-valued path

Subtree interval

Non-commutative operations

The classic off-by-one

Worked Query: Path 6 to 9

Why the Decomposition and Query Are Correct

Only logarithmically many light edges

The query covers exactly the path

Complexity Analysis

When can path queries become $O(\log N)$?

Implementation

Real-World Applications

Rooted network backbones

Hierarchy analytics

Game and dependency trees

Algorithmic query engines

Exercises

Trace the decomposition

Move from vertices to edges

Extend the range operations

Limitations

Static topology, dynamic data

Cookie Consent

Heavy-Light Decomposition (HLD)

Contents

Why Linearize a Tree?

The three-layer mental model

Heavy vs. Light Edges

The name is about the complement

Working Principle and Construction

Chains Become Array Ranges

head[u]

pos[u]

size[u]

parent[head[u]]

Path Queries and Updates

Vertex Values, Edge Values, and Operation Order

Vertex-valued path

Edge-valued path

Subtree interval

Non-commutative operations

The classic off-by-one

Worked Query: Path 6 to 9

Why the Decomposition and Query Are Correct

Only logarithmically many light edges

The query covers exactly the path

Complexity Analysis

When can path queries become $O(\log N)$?

Implementation

Real-World Applications

Rooted network backbones

Hierarchy analytics

Game and dependency trees

Algorithmic query engines

Exercises

Trace the decomposition

Move from vertices to edges

Extend the range operations

Limitations

Static topology, dynamic data

Related Deep Dives

Graph Theory Series

Lowest Common Ancestor (LCA)

Part 11: Trees & Minimum Spanning Trees

`head[u]`

`pos[u]`

`size[u]`

`parent[head[u]]`