102
правки
Изменения
Нет описания правки
'''Heavy-light декомпозиция''' {{---}} техника разбиения дерева на множество рёберно-непересекающихся путей так, чтобы при прохождении от одной вершины до другой произошла смена не более, чем <tex>O(\log{n})</tex> путей.
==Описание задачи==
Пусть у нас есть дерево <tex>T</tex> c <tex>n</tex> вершинами и нам нужно проводить операции на нем на пути от вершины <tex>v</tex> до вершины <tex>u</tex>. Множество подобных запросов делаются за время <tex>O(\log^p{n})</tex> при с помощью Heavy-light декомпозиции.
==Описание декомпозиции==
[[Файл:Heavylight.png|thumb|right|300x150px|Пример разбиения на лёгкие/тяжёлые рёбра.]]
