102
правки
Изменения
Нет описания правки
'''Heavy-light декомпозиция''' {{---}} техника разбиения подвешенного дерева на множество путей для решения задач о запросах на пути в дереве (в том числе с модификациями).
==Описание задачи==
{{Задача
|definition=Пусть у нас есть Имеется дерево <tex>T</tex> c <tex>n</tex> вершинами и нам нужно необходимо проводить операции на нем на пути от вершины <tex>v</tex> до вершины <tex>u</tex>. (Например сумма }}Примеры запросов:<ul><li>Сумма на пути</li><li>Максимум на пути</li><li>Количество рёбер на пути, вес которых больше заданного <tex>c</tex></li></ul> Примеры модификаций:<ul><li>Модификация одного ребра</li><li>Прибавление к весу всех рёбер на пути с модификацией прибавления </li><li>Установка веса всех рёбер на пути)}}в заданное <tex>c</tex></li></ul> Множество подобных запросов делаются за время за полином от логарифма (обычно <tex>O(\log^2{n})</tex> ) с помощью Heavy-light декомпозиции.
==Описание декомпозиции==
[[Файл:Heavylight.png|thumb|right|800x280px|Пример разбиения. В вершинах указан размер поддерева.]]
Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в 2 вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>.
'''Тяжёлые ребра(Heavy edge)''' {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geqslant</tex> <tex dpi="150">\frac{s(u)}{2}</tex>.
'''Лёгкие ребра(Light edge)''' {{---}} соответственно все остальные.
Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум <tex dpi="150">\frac{s(u)}{2}</tex> вершин, а также сама вершина <tex>u</tex>. Итого <tex>s(u) + 1</tex> вершин, тогда как у нас всего <tex>s(u)</tex> вершин в поддереве.
Теперь рассмотрим вершины, из которых не ведет вниз ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что полученная таким путём декомпозиция будет являться искомой и корректной.
{{Утверждение
|statement = Полученная декомпозиция является искомой.
# При прохождении пути от вершины <tex>v</tex> до вершины <tex>u</tex> произойдет смена не более, чем <tex>O(\log{n})</tex> путей. <br>Докажем эквивалентный факт, что при пути от любой вершины до корня мы сменим не более, чем <tex>O(\log{n})</tex> путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в 2 раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более <tex>O(\log{n})</tex> путей.
}}
Существует вариант Heavy-light декомпозиции на вершинно-непересекающихся путях. Чтобы получить такой путь нужно всего-лишь выкинуть последнее ребро из всех путей в рёберно-непересекающейся декомпозиции. Это может быть удобно при решении задач, где веса находятся не на рёбрах, а на вершинах и соответствующие запросы также делаются на вершинах.
==Применение==
Хоть это и не самый эффективный способ для решения этой задачи, но можно заметить, что с помощью такого трюка мы можем решить широкий класс задач просто сведя её к задаче о запросах в дереве отрезков (такие как максимум на пути, покраска на пути, прибавление на пути и др.).
==Реализация==
Опущены некоторые детали реализации: построение и предподсчёт. <ul><li><tex>\mathrm{getPath}</tex> {{---}} функция, позволяющая найти номер пути, относящийся к конкретной вершине, .</li> <li><tex>\mathrm{pathRoot}</tex> {{---}} функция, позволяющая найти корень пути (самая верхняя вершинасамую верхнюю вершину), .</li> <li><tex>\mathrm{pathPos}</tex> {{---}} функция, позволяющая найти смещение вершины в пути относительно корня пути, .</li><li><tex>\mathrm{getValue(\mathtt{i}, \mathtt{j})}</tex> {{---}} функция, позволяющая найти вес <tex>\mathtt{j}</tex>-ого ребра в <tex>\mathtt{i}</tex>-ом пути.</li></ul>
Пример реализации запроса суммы на пути:
<code>
'''functionint''' queryPath('''int''' path, '''int''' from, '''int''' to):
'''int''' res = 0
'''while''' from <= to:
'''if''' from % '''mod''' 2 == 1:
res += getValue(path, from)
'''if''' to % '''mod''' 2 == 0:
res += getValue(path, to)
to = (to - 1) / 2
'''return''' res
'''functionint''' query('''int''' u, '''int''' v):
'''int''' res = 0
'''int''' root = pathRoot(u)
'''while''' !isAncestor'''not''' (root, '''is ancestor of''' v) <font color=green>// поднимаемся до тех пор, пока наш путь не содержит общего предка u и v</font>
res += queryPath(getPath(u), 0, pathPos(u))
u = getParent('''parent of''' root) <font color=green>// вырезали нижний путь и подняли нижнюю вершину до нижней вершины следующего пути</font>
root = pathRoot(u)
root = pathRoot(v)
'''while''' !isAncestor'''not''' (root, '''is ancestor of''' u) <font color=green>// аналогично прошлому while, но с другой стороны</font>
res += queryPath(getPath(v), 0, pathPos(v))
v = getParent('''parent of''' root)
root = pathRoot(v)
<font color=green>// последний путь (тот, что содержит общего предка) обрезан с двух сторон полученными вершинами</font>
