arujbansal's blog

By arujbansal, 2 years ago, In English

Hey everyone,
I made a short video tutorial on the main idea behind Binary Lifting (a cool technique for answering tree related queries) and answering lowest common ancestor queries in O(log(N)) with it. Binary lifting can be used to answer other queries such as path sum, min, max, etc as well.

Euler Tours give us a lot of information about trees. One thing they can tell us is if some node u is an ancestor of some node v. This is a very nice problem related to this: 1328E - Tree Queries

I explain the version involving an Euler Tour. In my opinion, it is shorter to code than some other versions involving binary search and getting nodes to the same depth. You don’t need to know what Euler Tours are, I explain that. You just need to have a thorough understanding of what trees are and depth first search.

Check it out here: Binary Lifting Introduction
Here's how I like to implement it: My Implementation

 
 
 
 
  • Vote: I like it
  • +26
  • Vote: I do not like it