Lowest-Common-Ancestor-Binary-Lifting-and-HLD.md

Lowest Common Ancestor, Binary Lifting and HLD

Tutorial

• LCA and RMQ and its inter relation
• Binary Lifting and its usage in path queries
• Heavy Light Decomposition

Problems

1. For HLD, the blog has sufficient questions for practise and also includes editorials.

2. The questions given below are of LCA, binary lifting and advanced problems of HLD.

   • Q1-Easy
   • Q2-Easy
   • Q3-Medium
   • Q4-Medium
   • Q5-Medium/Hard
   • Q6-Hard
   • Q7-Very Hard
   • Q8-Very Hard

PS: Don’t get intimidated by the hardness of the problems. The easy basic and medium problems of HLD are covered in the tutorials. The ones of binary lifting/lca are in the easy/medium section and the hard and very hard problems consists of problems of HLD mixed with few other concepts making it very hard. If you are not able to solve them in your first try, don’t get disheartened.