Hello Guys.
I'm novice at competitive programming. I'm trying to learn LCA. Firstly I learned LCA O(n) going up the nodes (u and v) linearly. After I learned LCA O(sqrt(n)) using sqrt-decomposition spliting the graph in buckets. Now I trying learning the LCA using Sparse Table, but I don't understand how this tecninque works. Someone can explain me, and shows the implementaion or pseude-code ?
P.S.: Sorry my english. LOL :)
Lets store node's v 2^i-th parent at p[v][i]. And lets store depth of each node v at d[v]. When you calculate lca(u, v): first make sure, what depths are the same. Jump up to the lca using parents information. It can be seen from code, what you are doing binary search by depth:)
Good day to you,
Here is an awesome article about this. Maybe it is a littlebit longer (and maybe you'll need just the first part of it), it expplans RMQ-LCA very well...
Good Luck & Have Nice Day!
Thank you :)