102
правки
Изменения
Нет описания правки
==Описание декомпозиции==
[[Файл:Heavylight.png|thumb|right|800x280px|Пример разбиения. В вершинах указан размер поддерева.]]
Необходимо составить такую декомпозицию дерева на множество рёберно-непересекающихся путей, что при прохождении от одной вершины до другой произойдет смена не более <tex>O(\log{n})</tex> путей из декомпозиции.
Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в 2 вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>.
Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум <tex dpi="150">\frac{s(u)}{2}</tex> вершин, а также сама вершина <tex>u</tex>. Итого <tex>s(u) + 1</tex> вершин, тогда как у нас всего <tex>s(u)</tex> вершин в поддереве.
Теперь рассмотрим вершины, из которых не ведет вниз ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что полученная таким путём образом декомпозиция будет являться искомой и корректной.
{{Утверждение
==Применение==
===Сумма на пути===
Классическая задача о сумме на пути в дереве с <tex>n</tex> вершинами решается с помощью Heavy-light декомпозиции за время <tex>O(\log^2{n})</tex>. Возможны модификации веса.
Построим [[Дерево отрезков. Построение|дерево отрезков]] над каждым путём. Рассмотрим запрос <tex>sum(u, v)</tex>. Давайте найдем Найдем вершину <tex>c</tex>, которая является <tex>LCA(u, v)</tex> (например с помощью [[Метод двоичного подъема|двоичного подъема]]. Мы разбили запрос на два: <tex>(u, c)</tex> и <tex>(c, v)</tex>, на каждый из которых можно легко ответить выбирая путь, содержащий самую нижнюю вершину разбив его на множество путей из декомпозиции и вырезать его, пока этот ответив на каждый путь не содержит из этого множества по отдельности за <tex>cO(\log{n})</tex> с помощью дерева отрезков на этом пути. Всего таких путей нужно будет рассмотреть <tex>O(\log{n})</tex>. Итого мы способны решить эту задачу за время <tex>O(\log^2{n})</tex>.
===LCA===
Задача о наименьшем общем предке для двух вершин в дереве с <tex>n</tex> вершинами решается с помощью Heavy-light декомпозиции за время <tex>O(\log{n})</tex>.
Мы можем проверять, что вершина является предком другой вершины за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину. Тогда рассмотрим самый нижний путь (содержащий первую вершину) и посмотрим на его корень (самая высокая вершина в пути). Если эта вершина является предком второй вершины, то ответ где-то в этом пути, иначе выкинем этот путь и рассмотрим следующий вверх за ним.
Итого мы рассмотрели корень каждого пути за <tex>O(1)</tex>, а путей всего <tex>O(\log{n})</tex>. И в последнем пути один раз запустили бинпоиск, который отработал за <tex>O(\log{n})</tex>. Итоговая асимптотика <tex>O(\log{n})</tex>.
==Реализация==
Ниже будет приведена реализация запроса сумма на пути между любыми двумя вершинами в дереве без запросов модификации. Все запросы, сводящиеся к навешиванию дерева отрезков на пути из декомпозиции делаются похожим образом.
Опущены некоторые детали реализации: построение и дерево отрезков.
<ul>
'''int''' res = 0
'''int''' root = корень пути, в котором находится u
'''while''' root не является предком v: <font color=green>// поднимаемся до тех пор, пока наш путь не содержит общего предка u и v</font>
segmentTree = дерево отрезков, соответствующее путю в котором лежит u
res += segmentTree.sum(0, pathPos(u))
root = корень пути, в котором находится u
root = корень пути, в котором находится v
'''while''' root не является предком u: <font color=green>// аналогично прошлому while, но с другой стороны</font> segmentTree = дерево отрезков, соответствующее путю пути в котором лежит v
res += segmentTree.sum(0, pathPos(v))
v = предок root
root = корень пути, в котором находится v
<font color=green>// последний путь (тот, что содержит общего предка) обрезан с двух сторон полученными вершинами</font>
segmentTree = дерево отрезков, соответствующее путю пути в котором лежит u
res += segmentTree.sum(min(pathPos(u), pathPos(v)), max(pathPos(u), pathPos(v)))
'''return''' res
