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.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.04.2024 18:19:13 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
hey , i couldn't understood , HLD . i understood st and binary lifting .
Which parts did you not understand? I can try to explain it better.
how to apply HLD to a particular problem , where to use . and its variations. + how can we seperate heavy and light edges
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.
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
One segment tree for each set of connected heavy edges and one segment tree for each light edge.
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 .
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.
if we want to query maximum value on node bw any any nodes in a path why not simply use lca with binary lifting
HLD can also support updates in O(log N). Binary lifting can't.
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.
In my opinion, this was one of the best from your channel. Really enjoyed it. Thank you!