aneesh2312's blog

HLD vs Binary Lifting/Sparse Table
By aneesh2312, history, 7 years ago, In English

Does Heavy Light Decomposition have any advantage over Binary Lifting Technique or using a sparse table? Can we solve some type of problem using HLD which can't be solved using the other mentioned techniques?

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

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Hld is useful when u are given some kind of non-invertible operation queries with updates. For example, consider the problem witht the following 2 queries:

  1. Update the value of node X to Y

  2. Say the GCD of the path u...v

Can this be done in some other way ?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah ok, so it should be used when we need to support update queries. That didn't strike me for some reason. Thanks!

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Apart from update queries, ofc:

HLD: O(N) preprocessing, O(logN) LCA query, O(N) memory.
Binary lifting: O(NlogN) preprocessing, O(logN) LCA query, O(NlogN) memory.
Sparse table on DFS order: O(NlogN) preprocessing, O(1) LCA query, O(NlogN) memory.
Segment tree on DFS order: O(N) preprocessing, O(logN) LCA query, O(N) memory.

It's easy to see that HLD beats binary lifting by any means (except for simplicity which is actually quite important in CP), sparse table has a better query time but worse preprocessing time and memory complexity while segment tree gives you the same complexities. Not sure if the constant factor for querying segment tree is bigger than the one for LCA query in HLD but I guess so.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    HLD: O(N) preprocessing, O(logN) LCA query, O(N) memory.

    What do you mean by LCA query? LCA can be calculated in O(logN) irrespective of HLD/sparse tables, right?

    Maybe I have misunderstood what you meant but if you mean query a given path using HLD, that can take O(logN*logN) time, because you may encounter at most logN light edges and for each light edge you will perform a query on the segment tree representing the heavy path above it.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What I mean by LCA query is find the LCA of two nodes. You can do it with HLD, simply bringing one of the nodes to the next chain, depending on which one is deeper until they happen to be in the same chain.

      → Reply