Doubt in HLD - LCA and Sparse Table video

#1

What is the meaning of the line said - “we are storing 2 ki power j th parent of ith element” in our parent array. What this means?

#2

Any number can be expressed in binary. Set bit denotes that 2^ith bit is contributed to the number.
So suppose we want to find the 1st ancestor of a node , then the set 2^0th will give me the 1st ancestor.
Now let suppose we want to find the 3rd ancestor of a node , then we see the binary of 3 -> 011 , so we will first jump to the node at 2^0th ancestor and then from there we jump to the 2^1st ancestor of that node. In this way we end up at 3rd ancestor of node/
So storing every 2^ith ancestor for a node will be beneficial as we only ned log(n) bits for n nodes.

#3

So, basically we are doing binary lifting?

#4

Yes, it is also called binary lifting.

1 Like
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.