286
правок
Изменения
Нет описания правки
==Применение==
===Сумма на пути===
Классическая задача о сумме на пути в дереве с <tex>n</tex> вершинами может быть решена с помощью Heavyheavy-light декомпозиции за время <tex>O(\log^2{n})</tex>. Возможны модификации веса.
Построим [[Дерево отрезков. Построение|дерево отрезков]] над каждым путём. Рассмотрим запрос <tex>sum(u, v)</tex>. Найдем вершину <tex>c</tex>, которая является <tex>\mathrm{LCA}(u, v)</tex> (например с помощью [[Метод двоичного подъема|двоичного подъема]]. Мы разбили запрос на два: <tex>(u, c)</tex> и <tex>(c, v)</tex>, на каждый из которых можно легко ответить разбив его на множество путей из декомпозиции и ответив на каждый путь из этого множества по отдельности за <tex>O(\log{n})</tex> с помощью дерева отрезков на этом пути. Всего таких путей нужно будет рассмотреть <tex>O(\log{n})</tex>. Итого мы способны решить эту задачу за время <tex>O(\log^2{n})</tex>.
{{Лемма
|id=Лемма1
|statement=Пусть есть две вершины <tex>u</tex>, и <tex>v</tex>, лежащие на разных путях. При этом <tex>U</tex>, <tex>V</tex> — корни путей, на которых они лежат. Если <tex>U</tex> более удален от корня, чем <tex>V</tex>, то <tex>\mathrm{LCA}(u, v) = \mathrm{LCA}(U, v)</tex>.
|proof=Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}</tex> не равны. Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Значит <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию.
Построим heavy-light декомпозицию для данного нам дерева. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:
# Расстояние до корня дерева. <br />Вычисляется за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину.
# Корень пути, на котором лежит вершина. <br />Из всех путей выбираем Поскольку вершина может принадлежать нескольким путям, выберем тот, чья начальная вершина наиболее удалена от корня дерева. Очевидно, что имея Имея разбиение на пути, найти корень можно за <tex>O(1)</tex>.
# Вторая вершина этого пути. <br />Аналогично, находится за <tex>O(1)</tex> при построении.
Ниже представлен псевдокод функции получения наименьшего общего предка:
<font color=darkgreen>// Находит наименьшего общего предка вершин <tex>u</tex> и <tex>v</tex></font>
'''else''':
'''return''' v
<font color=darkgreen>// Рекурсивно запустимся от вершины, чей предок наиболее удален от корня.</font>
'''if''' (dist[last[u]] > dist[last[v]]):
'''return''' lca(last[u], v)
'''return''' lca(last[v], u)
====Асимптотика====
</ul>
Пример реализации запроса суммы на пути:
'''int''' query('''int''' u, '''int''' v):
'''int''' res = 0
'''int''' root = корень пути, в котором находится u
'''while''' root не является предком v <font color=green> // поднимаемся до тех пор, пока наш путь не содержит общего предка u и v</font>
segmentTree = дерево отрезков, соответствующее пути, в котором лежит u
res += segmentTree.sum(0, pathPos(u))
u = предок root <font color=green> // вырезали нижний путь и подняли нижнюю вершину до нижней вершины следующего пути</font>
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
== См.также ==
