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

Binary Lifting
Автор YogeshZT, история, 9 месяцев назад, По-английски

Hello, I was solving the question which involves finding Kth ancestor of a node in a tree using binary lifting. I was wondering if instead of binary lifting, is there something like n-ary lifting (n>2 ofc). Is it something which can be thought of and will it be more efficient?

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

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

N-ary lifting is somewhat useful only if you're trying to squeeze your solution into the tight memory limit

For example, if you take N = 4, you have to store two time less data relatively to the classic binary lifting (4th, 16th, 64th, ..., 4^kth ancestors): answering the query is basically the same except of some casework with small queries, which is doable in O(1)

Moreover, the same trick is applicable to the sparse table — same as in the binary lifting, it allows to trade some constant factor in time for some constant factor in memory

→ Ответить