Open In App

Introduction to Heavy Light Decomposition

Last Updated : 23 Dec, 2022
Improve
Improve
Like Article
Like
Save
Share
Report

Heavy Light decomposition (HLD) is one of the most used techniques in competitive programming.

Example Problem: Let us understand Heavy-light decomposition (HLD) with the help of below example.

Suppose we have an unbalanced tree (not necessarily a Binary Tree) of n nodes, and we have to perform operations on the tree to answer a number of queries, each can be of one of the two types:

  1. change(a, b): Update weight of the ath edge to b.
  2. maxEdge(a, b): Print the maximum edge weight on the path from node a to node b. For example maxEdge(5, 10) should print 25.

Assume that nodes are numbered from 1 to n. There must be n-1 edges. Edge weights are natural numbers. Also assume that both type of queries are interspersed (approximately equal in number), and hence no type can be sidelined to compromise on complexity.

hld1

Simple Solution: A Simple solution is to traverse the complete tree for any query. Time complexity of every query in this solution is O(n).

HLD Based Solution:

Upon careful observation of the two operations, we realize that we have seen them somewhere. Eureka! Segment Trees. A Segment Tree can be used to perform both types in O(log(n)). But wait! A Segment Tree can be built from a one-dimensional array / chain (set of nodes linked one after another), and what we have here is a tree. So, can we reduce the tree to chains?

The HLD based solution discussed in the post takes O(log2(n)) for maxEdge() and O(log n) for change().

Size of a node x is number of nodes in subtree rooted with the node x. Here is an image showing subtree sizes of each node written on top of them:
hld2

HLD of a rooted tree is a method of decomposing the vertices of the tree into disjoint chains (no two chains share a node), to achieve important asymptotic time bounds for certain problems involving trees.

HLD can also be seen as ‘coloring’ of the tree’s edges. The ‘Heavy-Light’ comes from the way we segregate edges. We use size of the subtrees rooted at the nodes as our criteria.

An edge is heavy if size(v) > size(u) where u is any sibling of v. If they come out to be equal, we pick any one such v as special.

hld3

change(u, v) operation:
Since Segment Tree is used as underlying data structure to represent individual chains, change is done using update of segment tree. So the time complexity of change operation is O(Log n).

maxEdge(u, v) operation:

    1. We first find LCA of two nodes. Say node u is 11 and node v is 9. Their LCA is node 1.
    2. Then we crawl up the tree from node u to the lca. If node u and lca belong to the same chain, we find the maximum from the range that represents the edges between them using segment tree. Else, we find the maximum from the chain to which u belongs, then change chains and repeat while we are not in the same chain.
    3. We repeat the same step (as step 2) from v to lca and return maximum of two weights.

As per our example above, let’s take u as node 11 and v as node 9. LCA is node 1. We move from node 11 to node 1, and we change chains once. When we change chains, we shift from our queried node to the parent of head of the chain to which it belongs (11 changes to 8 here). Similarly node 9 to node 3 queried (including the light edge), and chain changed (node changed to 1).

Heavy Light Decompostion

hld8

Time Complexity of maxEdge is O(log2(n)). Querying maximum of a chain takes O(log(n)) time as chains are represented using Segment Tree and there are at-most O(log(n)) chains.

How is the number of chains O(log(n))?
All chains are connected by a light edge (see above examples). So the number of chains is bounded by number of light edges on any path. If we follow a light edge from the root, the subtree rooted at the resulting vertex has at most n/2 size. If we repeat, we land at a vertex with subtree size at most n/4, and so on. We conclude that number of light edges on any path from root to leaf is at most log(n) (Source: wcipeg)

The main idea of Heavy Light Decomposition of a unbalanced tree is to club vertices of long (or heavy) paths together in chains so that these linear chains can be queried in O(Log n) time using a data structure like Segment Tree.

In the next article, segment tree representation of chains in more detail and implementation of HLD solution for the problem is discussed as example.

Heavy Light Decomposition | Set 2 (Implementation)


Y

Yash Varyani
Improve
Previous Article
BFS using STL for competitive coding
Next Article
Meet in the middle

Similar Reads

Implementation of Heavy Light Decomposition
We strongly recommend to refer below post as a prerequisite of this.Heavy Light Decomposition | Set 1 (Introduction)In the above post, we discussed the Heavy-light decomposition (HLD) with the help of below example. Suppose we have an unbalanced tree (not necessarily a Binary Tree) of n nodes, and we have to perform operations on the tree to answer
15+ min read
Cholesky Decomposition : Matrix Decomposition
In linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions. One of them is Cholesky Decomposition. The Cholesky decomposition or Cholesky factorization is a decomposition of a Hermitian, positive-definite matrix into the product of a low
9 min read
Puzzle | Weight of Heavy Ball
Puzzle: There are 2187 balls, out of which 1 is heavy. Find the minimum number of attempts the balls have to be weighed for finding out the heavy ball. Solution: The minimum amount of measurements needed to be done will be equal to 7 times. 2187 = 3^7 Step 1: Divide the 2187 balls into 3 equal groups of 729 each, let's say C1, C2 and C3. Put C1 on
4 min read
MO's Algorithm (Query Square Root Decomposition) | Set 1 (Introduction)
Let us consider the following problem to understand MO's Algorithm.We are given an array and a set of query ranges, we are required to find the sum of every query range. Example: Input: arr[] = {1, 1, 2, 1, 3, 4, 5, 2, 8}; query[] = [0, 4], [1, 3] [2, 4] Output: Sum of arr[] elements in range [0, 4] is 8 Sum of arr[] elements in range [1, 3] is 4 S
15+ min read
Sum of decomposition values of all suffixes of an Array
Given an array arr[], the task is to find the sum of the decomposition value of the suffixes subarray.Decomposition Value: The decomposition value of a subarray is the count of the partition in the subarray possible. The partition in the array at index [Tex]i [/Tex]can be done only if the elements of the array before if it less than the current ind
8 min read
Singular Value Decomposition (SVD)
The Singular Value Decomposition (SVD) of a matrix is a factorization of that matrix into three matrices. It has some interesting algebraic properties and conveys important geometrical and theoretical insights about linear transformations. It also has some important applications in data science. In this article, I will try to explain the mathematic
6 min read
Calculate sum in Diagonal Matrix Decomposition by removing elements in L-shape
Given two integers N representing the dimension of a square matrix and an integer A with which the matrix is initialized. Given another integer mod. Calculate the required sum by following the given steps: Select the product of all elements in L shape beginning from the topmost right element, add it to the sum and remove all of them from the matrix
6 min read
K-shell decomposition on Social Networks
Prerequisite: Introduction to Social Networks K-shell decomposition is the method in which we can divide nodes on the basis of the number of its degree like nodes with degree 1 in one bucket etc. Consider an example, assume there are n nodes and you apply k-shell decomposition in it. So nodes with degree 1 will be in bucket1 then we will see that a
4 min read
Range Minimum Query (Square Root Decomposition and Sparse Table)
We have an array arr[0 . . . n-1]. We should be able to efficiently find the minimum value from index L (query start) to R (query end) where 0 <= L <= R <= n-1. Consider a situation when there are many range queries. Example: Input: arr[] = {7, 2, 3, 0, 5, 10, 3, 12, 18}; query[] = [0, 4], [4, 7], [7, 8]Output: Minimum of [0, 4] is 0 Minim
15+ min read
Centroid Decomposition of Tree
Background : What is centroid of Tree? Centroid of a Tree is a node which if removed from the tree would split it into a ‘forest’, such that any tree in the forest would have at most half the number of vertices in the original tree. Suppose there are n nodes in the tree. ‘Subtree size’ for a node is the size of the tree rooted at the node. Let S(v)
15+ min read
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox