DiegoCosta's blog

By DiegoCosta, history, 13 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  

»
13 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;
}
»
13 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!

»
13 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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please could you explain how can I reduce O(n^2) to O(n). Thanks a lot.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Using Stack ??

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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!