WalidMasri's blog

What algorithm do you use to find LCA?
By WalidMasri, history, 8 years ago, In English

Hello codeforces!

I recently got interested in the LCA problem and read a lot about it. I learned three methods for computing LCA queries:

  • Using Sparse Table (But i didn't like that approach since the 2-d array gives me outofmemory exception when number of nodes is 10^5 )

  • Transforming my rooted tree into an array and apply segment trees on it. This method works well for me but takes much too long to code.

  • Using Union-Find data structure.

Which approach do you use and why? Thanks!

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I use ST. I think it's the most convinient one.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If the time and memory limits allow it, I would go for binary lifting method. Otherwise, I will most likely code heavy-light decomposition which gives O(N) preprocessing, O(N) memory and O(logN) per query :)

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it -16 Vote: I do not like it

    Nice! but binary lifting is slow with a query of O(log^2 n)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Actually it's O(logN), what makes it worse than HLD is the preprocessing time and memory complexity both of O(NlogN). But it's much easier to code so that's my first choice if the memory and time limit allow it, as I said :)

      → Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I use sparse table (parent[lgN][N]) as it's easy to code and doesn't require any additional knowledge (segment trees).
BTW, if N=100000, 4*17*100000 = 6.8 MB. Where is your MLE?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how is it [logN][N] ? My implementation use parent[N][N] Can you provide a code of your approach?

    Thanks!

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      Seems that you haven't learned anything, lol. Here you are: 10077331

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can implement HLD without Segment Tree, and it works for LCA problems. Easier to code for me. Which one do you find faster in practice ??

    → Reply