DiegoCosta's blog

By DiegoCosta, history, 7 months ago, In English,

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

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

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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]<d[v])
swap(u, v);
for(int i=log;i>=0;i--)
{
if(d[p[u][i]]<d[v])
u=p[u][i];
}

for(int i=log;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;
}
»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it