### Updown's blog

By Updown, 7 months ago, ,

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.

• +45

 » 7 months ago, # |   0 hey , i couldn't understood , HLD . i understood st and binary lifting .
•  » » 7 months ago, # ^ |   0 Which parts did you not understand? I can try to explain it better.
•  » » » 7 months ago, # ^ |   0 how to apply HLD to a particular problem , where to use . and its variations. + how can we seperate heavy and light edges
•  » » » » 7 months ago, # ^ |   0 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.
•  » » » » » 7 months ago, # ^ |   0 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
•  » » » » » » 7 months ago, # ^ |   0 One segment tree for each set of connected heavy edges and one segment tree for each light edge.
•  » » » » » » » 7 months ago, # ^ | ← Rev. 3 →   0 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 .
•  » » » » » » » » 7 months ago, # ^ |   +1 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.
•  » » » » » » » » » 7 months ago, # ^ |   0 if we want to query maximum value on node bw any any nodes in a path why not simply use lca with binary lifting
•  » » » » » » » » » 7 months ago, # ^ |   +6 HLD can also support updates in O(log N). Binary lifting can't.
•  » » » » » » » 7 months ago, # ^ |   0 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.
 » 7 months ago, # |   +3 In my opinion, this was one of the best from your channel. Really enjoyed it. Thank you!