Блог пользователя fck_cheater

Автор fck_cheater, история, 3 года назад, По-английски

Can all the heavy-light decomposition (HLD) problems be solved using Binary lifting technique or do I need to learn HLD too? Thanks for helping, I am new to this field.

Extra: Stress away

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

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

HLD seems to be more difficult and has worse complexity, but it's somehow well-known. Of course, there exists a problem, that requires HLD.

To be more certain, binary lifting technique allows you to calculate some value over some path. Heavy-light decomposition allows it too, but it also allows updates. You can't update fast all precomputed values for binary lifting. If $$$n = 2^k$$$ for some $$$k$$$, there could be $$$n / 2$$$ ways of length $$$n / 2$$$ over a vertex. It is already too many.