102
правки
Изменения
Нет описания правки
}}
==Примеры Применение=====Сумма на пути===Классическая задача о сумме на пути в дереве с <tex>n</tex> решается с помощью Heavy-light декомпозиции за время. Возможны модификации веса. Построим [[Дерево отрезков. Построение|дерево отрезков]] над каждым путём. Рассмотрим запрос <tex>sum(u, v)</tex>. Давайте найдем вершину <tex>c</tex>, которая является <tex>LCA(u, v)</tex> (например с помощью [[Метод двоичного подъема|двоичного подъема]]. Мы разбили запрос на два: <tex>(u, c)</tex> и <tex>(c, v)</tex>, на каждый из которых можно легко ответить выбирая путь, содержащий самую нижнюю вершину и вырезать его, пока этот путь не содержит <tex>c</tex>. Так мы сможем получать ответ на пути за <tex>O(\log{n})</tex>. А всего таких путей нужно будет рассмотреть <tex>O(\log{n})</tex>. Итого мы способны решить эту задачу за время <tex>O(\log^2{n})</tex>. Хоть это и не самый эффективный способ для решения этой задачи, но можно заметить, что с помощью такого трюка мы можем решить широкий класс задачпросто сведя её к задаче о запросах в дереве отрезков (такие как максимум на пути, покраска на пути, прибавление на пути и др.).==Реализация==Some examplesЗдесь будет простая реализация Heavy-light декомпозиции
