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

How do you usually implement HLD with segment tree?
Автор WRKWRK, история, 13 месяцев назад, По-английски

Heavy-Light Decomposition with segment tree.

Do you flatten the tree by DFS (prioritizing the heavy child) and use a single segment tree over the whole array,

or build a separate segment tree for each chain?

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

»
13 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by WRKWRK (previous revision, new revision, compare).

→ Ответить
»
13 месяцев назад, скрыть # |
 
Проголосовать: нравится +27 Проголосовать: не нравится

who tf uses second method?

→ Ответить
»
13 месяцев назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

The second method cannot handle subtree information, but the first method can.

→ Ответить
»
13 месяцев назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

first method is really convenient

→ Ответить
»
13 месяцев назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

I usually use the 2nd method as it make the indexing easier, as I'm already using a pointer based segment tree most of the time.

For speed usually both are the same in my experience:

  • First method can benefit from array based segment tree, but for every chain you have to get from some part of the whole tree.

  • Second method only need to get from specific smaller tree, so it's lower amount of node.

The 2nd method also has the added benefit of being a lot faster when your data structure can support faster prefix query:

  • Except for the last chain, for every chain you will query a prefix and not a middle range.

  • So if you can get a prefix in a lower complexity (or at least smaller constant), you only pay for the mid range query at the last chain.

→ Ответить