### DiegoCosta's blog

By DiegoCosta, history, 18 months ago, ,

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 :)

• +5

 » 18 months ago, # | ← Rev. 3 →   0 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:) lca(u, v) { if(d[u]=0;i--) { if(d[p[u][i]]=0;i--) { if(pa[u][i]!=pa[v][i]) { u=pa[u][i]; v=pa[v][i]; } } while(u!=v) { u=pa[u][0]; v=pa[v][0]; } return u; } 
 » 18 months ago, # |   +5 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!
•  » » 18 months ago, # ^ |   +5 Thank you :)
 » 18 months ago, # |   0 The ancestors of a node is represented in power of two, and every number can be represented in binary form in only one way, so it's possible to cut down the complexity to logarithmic complexity. You may watch videos instead, for better visualisation.
 » 18 months ago, # |   0 You can find the video link to tutorial here : http://algorithms-live.blogspot.in/2017/07/episode-28-sparse-tables-and-lca.html?m=1
 » 6 months ago, # |   0 Hi there, I am trying to solve this problem with sparse table, I am getting TLE on this problem.Here is what I tried. Can soneone solve this problem with sparse table Thanks in advance.
•  » » 6 months ago, # ^ |   0 Hey, first of all, there is nothing wrong with your implementation of Sparse Table, and you're not getting TLE because of it.The TLE is because of the loops in line 145-151, which makes your code run in O(n^2) in addition to O(nlogn) preprocessing. Try to make the implementation O(n)!P.S It is possible to do it in O(n), using the NGE concept!
•  » » » 6 months ago, # ^ |   0 Please could you explain how can I reduce O(n^2) to O(n). Thanks a lot.
•  » » » » 6 months ago, # ^ |   0 Using Stack ??
•  » » » » » 6 months ago, # ^ |   0 Yes, try counting the number of times each element will be added, i.e will appear as a maximum in a subarray, also count the number of times each element will be negated, i.e will appear as the minimum in a subarray. The answer will be the summation of the product of the two quantities for all the elements!Hope it helps!
 » 2 months ago, # |   0 Well Implementation: Link