🌳 Heavy-Light Decomposition (HLD) – Comprehensive Study Guide

**Heavy-Light Decomposition (HLD)** is a **tree decomposition technique** that allows us to efficiently process **path queries and updates** in **O(log² N)** time using **Segment Tree or Fenwick Tree**.

⚡ Why Use HLD?

  • ✅ **Fast path queries in O(log² N) instead of O(N).**
  • 🚀 **Efficiently handles dynamic updates in trees.**
  • 🔍 **Useful in Lowest Common Ancestor (LCA) queries.**
  • 📡 **Essential for competitive programming (ICPC, Codeforces, AtCoder).**

📌 Understanding Heavy & Light Edges

📥 **1. Heavy Edges**

The **edge connecting a parent node** to the **child node with the largest subtree**.

📤 **2. Light Edges**

All other edges that do not belong to the heavy path.

📌 Breaking the Tree into Heavy & Light Paths

📌 Step-by-Step Process:

  1. ✅ Find the **size of each subtree**.
  2. 📌 Identify the **child with the largest subtree** (Heavy Child).
  3. 🔄 Connect all **heavy children** into **heavy paths**.
  4. 🔗 Light edges remain separate & can be handled separately.

🛠️ Heavy-Light Decomposition Implementation

📌 **1. DFS to Compute Subtree Sizes**


                vector> tree;
                vector parent, depth, subtreeSize, heavyChild;
            
                int dfs(int node, int par) {
                    parent[node] = par;
                    subtreeSize[node] = 1;
                    int maxSubtree = 0;
            
                    for (int child : tree[node]) {
                        if (child == par) continue;
                        depth[child] = depth[node] + 1;
                        int childSize = dfs(child, node);
                        subtreeSize[node] += childSize;
            
                        if (childSize > maxSubtree) {
                            maxSubtree = childSize;
                            heavyChild[node] = child;
                        }
                    }
                    return subtreeSize[node];
                }

📌 **2. Building Heavy-Light Chains**


                vector chainHead, positionInBase, baseArray;
                int chainCount = 0, pos = 0;
            
                void hld(int node, int head) {
                    chainHead[node] = head;
                    positionInBase[node] = pos++;
                    baseArray.push_back(node);
            
                    if (heavyChild[node] != -1)
                        hld(heavyChild[node], head);
            
                    for (int child : tree[node]) {
                        if (child != parent[node] && child != heavyChild[node])
                            hld(child, child); // Start a new chain
                    }
                }

📏 Path Queries Using Segment Tree

📌 **1. Updating Values in a Path (O(log² N))**


                int queryPath(int u, int v) {
                    int result = 0;
            
                    while (chainHead[u] != chainHead[v]) {
                        if (depth[chainHead[u]] < depth[chainHead[v]]) swap(u, v);
                        result += segmentTree.query(positionInBase[chainHead[u]], positionInBase[u]);
                        u = parent[chainHead[u]];
                    }
                    
                    if (depth[u] > depth[v]) swap(u, v);
                    result += segmentTree.query(positionInBase[u], positionInBase[v]);
                    return result;
                }

📌 **2. Finding Lowest Common Ancestor (LCA) Using HLD**


                int LCA(int u, int v) {
                    while (chainHead[u] != chainHead[v]) {
                        if (depth[chainHead[u]] < depth[chainHead[v]]) swap(u, v);
                        u = parent[chainHead[u]];
                    }
                    return (depth[u] < depth[v]) ? u : v;
                }

⏳ Time Complexity Analysis

Operation Time Complexity
Preprocessing (DFS & HLD) O(N)
Path Query O(log² N)
Point Update O(log N)
Lowest Common Ancestor (LCA) O(log N)

🌍 Real-World Applications of HLD

  • 📡 **Network Routing** – Fast processing of **network queries**.
  • 🎮 **Game Development** – Efficient **region queries** in maps.
  • 🔄 **Tree-Based DP Problems** – Queries on **subtree sums**.
  • 🗂 **File System Optimization** – Managing **hierarchical structures**.

🔗 Next Topics