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
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
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 ^_^