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

Автор aneesh2312, история, 7 лет назад, По-английски

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?

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.