286
правок
Изменения
Нет описания правки
==Применение==
===Сумма на пути===
Классическая задача о сумме на пути в дереве с <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>O(\log{n})</tex> с помощью дерева отрезков на этом пути. Всего таких путей нужно будет рассмотреть <tex>O(\log{n})</tex>. Итого мы способны решить эту задачу за время <tex>O(\log^2{n})</tex>.
Хоть это и не самый эффективный способ для решения этой задачи, но можно заметить, что навесив дерево отрезков на каждый путь мы способны отвечать на любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на моноиде (операции, поддерживаемые деревом отрезков), такие как: сумма на пути, максимум на пути, количество рёбер на пути, удовлетворяющих какому-то свойству.
===LCA===
Задача о наименьшем общем предке для двух вершин в дереве с <tex>n</tex> вершинами решается также может быть решена с помощью heavy-light декомпозиции. Воспользуемся основной идеей: декомпозиция разбивает все вершины дерева на реберно-непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>\log{n}</tex> различных путей.
{{Лемма
|id=Лемма1
|statement=Пусть есть две вершины <tex>au</tex>, <tex>bv</tex>, лежащие на разных путях. Пусть При этом <tex>AU</tex>, <tex>BV</tex> - — корни путей, на которых они лежат. Пусть Если <tex>AU</tex> более удален от корня, чем <tex>BV</tex>. Докажем, что то <tex>LCA(au, bv) </tex> = <tex>LCA(AU, bv)</tex>.
|proof=Пусть пути не пересекаются. Предположим, что LCA не равны. Значит существует вершина, на пути от <tex>au</tex> к <tex>AU</tex>, являющаяся LCA. Но LCA должен принадлежать двум путям. Но Однако пути на пересекаются. Тем самым пришли к противоречию.
Рассмотрим случай, когда пути пересекаются. Пути не могут пересекаться более, чем в одной вершине. В данном случае корень одного из путей является вершиной другого. LCA должен принадлежать двум путям, значит именно этот корень и будет LCA.
