Updown's blog

Heavy Light Decomposition Video Tutorial
By Updown, 6 years ago, In English

Hi CodeForces!

Last week I streamed about LCA (least common ancestor), Segment trees, and Heavy Light Decomposition. You can check out the stream here. If you already know one or more of those concepts, you can jump to the other concepts.

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hey , i couldn't understood , HLD . i understood st and binary lifting .

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

    Which parts did you not understand? I can try to explain it better.

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

      how to apply HLD to a particular problem , where to use . and its variations. + how can we seperate heavy and light edges

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

        Think of HLD as a segment tree on a tree. Let's say that each edge on a tree has a value and you want to query the min/max/sum of the values on a path in the tree.

        To separate heavy and light edges, we start at the root. The edge leading into subtree with the most nodes is heavy and all the other edges going out of the root are light. Repeat at every node. There should not be two adjacent light edges. Two adjacent heavy edges means that they are part of the same segtree.

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

          so , for each heavy edge do we have to build a new segment tree or only one segment tree can cover all heavy edges and one segment tree for light edges

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

            One segment tree for each set of connected heavy edges and one segment tree for each light edge.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              ok . what to query and how to query ? + do u have implementation of HLD which you frequently use in contest . can you share it with me .

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                What to query depends on the problem you are trying to solve.
                Maybe you want to find the maximum value node on the path between some 2 nodes. Then you would query for the maximum value in the segment trees you encounter, and choose the maximum one.

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

                  if we want to query maximum value on node bw any any nodes in a path why not simply use lca with binary lifting

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

                  HLD can also support updates in O(log N). Binary lifting can't.

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

              If you relabel the nodes so that all the nodes in a chain are next to each other (dfs order), you can use one segment tree for the whole tree. makes the implementation easier imo.

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

In my opinion, this was one of the best from your channel. Really enjoyed it. Thank you!

→ Reply