CODEWITHSUNDEEP
algorithmgraphtree
rimbaerl
rimbaerl

Reputation: 31

Which algorithm is best to use for finding LCA in tree?

I am interested in finding the distance of two nodes in a tree, in a least complexity possible. The finding process is in some queries and updates on the tree (adding and deleting a node).

This problem can use LCA as the tool for optimization. However, by these posts I found, there are some algorithm available.

https://cp-algorithms.com/graph/lca.html https://cp-algorithms.com/graph/lca_binary_lifting.html

Here is the summary,

  1. LCA + Sqrt Decomposition

Preprocessing time: O(N)

Query time: O(√N)

Allow to update tree: Yes

  1. LCA + Segment Tree

Preprocessing time: O(N)

Query time: O(log N)

Allow to update tree: Yes

  1. LCA + Sparse Table

Preprocessing time: O(N log N)

Query time: O(1)

Allow to update tree: No

  1. LCA + Binary Lifting

Preprocessing time: O(N log N)

Query time: O(log N)

Allow to update tree: Yes

My question is, what is the best algorithm best to use?

Or which algorithm is best to use under what conditions?

Are there any other advantages or drawbacks that is not mentioned above for each algorithm?

Upvotes: 3

Views: 660

Answers (1)

Photon
Photon

Reputation: 2777

From personal experience as competitive programmer:

  • LCA + Sqrt Decomposition - never used this one, seems quite slow query time
  • LCA + Segment Tree - this one is quite good the only downside being a bit tedious to code - I rarely use this, usually on some problems where segment tree is already required (i.e. Heavy Light Decomposition)
  • LCA + Sparse Table - that O(1) query time is a must for some problems even though they might be rare
  • LCA + Binary Lifting - the one I use 90% of the time - easy to code and quite fast

Upvotes: 3

Related Questions