DiegoCosta's blog

LCA with Sparse Table
By DiegoCosta, history, 6 years 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

Comments Comments (3)
| Write comment?
»
6 years 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;
}
→ Reply
»
6 years 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!

→ Reply