Блог пользователя AMR-KELEG

Автор AMR-KELEG, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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