Блог пользователя DiegoCosta

LCA with Sparse Table
Автор DiegoCosta, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, # |
← 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]<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;
}
→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +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!

→ Ответить