This is a long post with lot of explanation, targeting novice. If you are aware of how HLD is useful, skip to “Basic Idea”.
A balanced binary tree with N nodes has a height of log N. This gives us the following properties:
- You need to visit at most log N nodes to reach root node from any other node
- You need to visit at most 2 * log N nodes to reach from any node to any other node in the tree
The log factor is always good in the world of competitive programming 🙂
Now, if a balanced binary tree with N nodes is given, then many queries can be done with O( log N ) complexity. Distance of a path, Maximum/Minimum in a path, Maximum contiguous sum etc etc.