Graph Theory37 sections · 1633 units
Open in Course

Lessons - Path Queries II

(When to use HLD)

Lesson: path queries with updates require Heavy-Light Decomposition. The keyword here is "updates." If there were no updates, you could use LCA with preprocessing (precompute all path values).

But updates break preprocessing. You need a data structure that recomputes answers quickly. HLD is that structure. It is overkill for static trees, but necessary when values change. Each update or query costs O(log2n)O(\log^2 n), which is fast enough for most competitive programming problems.