Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

AMR-KELEG's blog

Can LCA (Least Common Ancestor) be used instead of HLD (Heavy Light Decomposition)?
By AMR-KELEG, history, 9 years ago, In English

I have lately learned how to use the LCA algorithm.

I am now wondering whether HLD can be used to solve problems that LCA can't solve or not?

What are your thoughts?

Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

Good day to you,

Well in my opinion this is hardly answered, since LCA is more-like "problem" than algorithm (or group of algorithms), which can be solved with multiple algorithms, such as: HLD, Binary Lifting, EulerTourTree+SparseTable, Tarjan, DP, simple dfs and so on.

Probably each of them has some draw-backs/advantages.

So more-like: HLD is a kind of "LCA algorithms".

The big advantage of HLD is, that is can easily divide the tree, so one can "dynamicaly update" with decent access time [+ it is easy to grapple many structures to the decomposed tree].

Also — it can be (unlike some other LCA algorithms) used in opposite way: to "write" an information to multiple nodes "at once" [like in segment tree ... or well, basically with usage of segment tree {or similar} :) ]

Have Nice Day & Good Luck ^_^

→ Reply