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 :) Comments (11)
 » 18 months ago, # | ← Rev. 3 →   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]; v=pa[v]; } return u; } 
 » 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 :)
 » 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.
 » 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
 » 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.
•  » » 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!
•  » » » Please could you explain how can I reduce O(n^2) to O(n). Thanks a lot.
•  » » » » Using Stack ??
•  » » » » » 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!