Senior LevelData Structures & Algorithms
What is Heavy-Light Decomposition (HLD) and what problems does it solve?
❓ Interview Prompt: Explain Heavy-Light Decomposition, path decomposition into O(log N) chains, and enabling O(log²N) path queries on trees.
Heavy-Light Decomposition decomposes a tree into a set of chains such that any root-to-leaf path crosses at most $O(\log N)$ chains.
Concept:
•
Heavy Edge: For each non-leaf node, the edge to the child with the largest subtree size is the heavy edge.
•
Chain: Maximal path of consecutive heavy edges.
•
Any path between two nodes crosses $O(\log N)$ chains.
Usage:
Combine HLD with a Segment Tree on flattened chain arrays to:
•
Answer path sum/min/max queries in $O(\log^2 N)$.
•
Handle point/range updates on paths in $O(\log^2 N)$.
Applications: Competitive programming, interval tree queries on hierarchical data.
Code Implementation Example
typescript
// HLD core: compute subtree sizes and heavy children
function computeHLD(
root: number,
adj: number[][],
parent: number[],
subtreeSize: number[],
heavyChild: number[]
): void {
function dfs(u: number, p: number): void {
subtreeSize[u] = 1;
parent[u] = p;
let maxSize = 0;
heavyChild[u] = -1;
for (const v of adj[u]) {
if (v === p) continue;
dfs(v, u);
subtreeSize[u] += subtreeSize[v];
if (subtreeSize[v] > maxSize) {
maxSize = subtreeSize[v];
heavyChild[u] = v;
}
}
}
dfs(root, -1);
}
// After HLD: flatten chains to array, apply Segment Tree for O(log²N) path queries💡HLD preprocessing — computing subtree sizes and heavy children.
🎯 Interview Key Takeaway
HLD reduces tree path queries to segment tree range queries by guaranteeing O(log N) chain crossings per path. Essential for O(log²N) tree path problems.
#DSA#Heavy-Light Decomposition#Tree#Advanced#Senior
Back to all Data Structures & Algorithms Questions→