What algorithm do you use to find LCA?

Revision en1, by WalidMasri, 2016-02-03 22:21:05

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English WalidMasri 2016-02-03 22:21:05 547 Initial revision (published)