WRKWRK's blog

How do you usually implement HLD with segment tree?
By WRKWRK, history, 13 months ago, In English

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?

  • Vote: I like it
  • +26
  • Vote: I do not like it

»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
13 months ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

who tf uses second method?

→ Reply
»
13 months ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
13 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

first method is really convenient

→ Reply
»
13 months ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

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.

→ Reply