fck_cheater's blog

Pls help me with this
By fck_cheater, history, 3 years ago, In English

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

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply