Изменения

'''Heavy-light декомпозиция''' {{---}} техника разбиения дерева на множество рёберно-непересекающихся путей так, чтобы при прохождении от одной вершины до другой произошла смена не более, чем <tex>Oдля решения задач о запросах на пути в дереве (\log{n}в том числе с модификациями)</tex> путей.

{{Задача|definition=Пусть у нас есть дерево <tex>T</tex> c <tex>n</tex> вершинами и нам нужно проводить операции на нем на пути от вершины <tex>v</tex> до вершины <tex>u</tex>. (Например сумма на пути с модификацией прибавления на пути)}}Множество подобных запросов делаются за время <tex>O(\log^p2{n})</tex> с помощью Heavy-light декомпозиции.

'''Тяжёлые ребра''' {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geqgeqslant</tex> <tex dpi="150">\frac{s(u)}{2}</tex>.

 1. # Все рёбра покрыты путями. <br>Есть два типа вершин: те, из которых ведёт ровно одно тяжёлое ребро и те, из которых не ведёт ни одного тяжёлого ребра. Для первого типа вершин мы дойдем до них некоторым путём через тяжёлое ребро снизу по определению выбора путей, а лёгкие рёбра ведущие из неё возьмем как последние рёбра в соответствующих путях. Для второго типа вершин мы по определению выбора путей возьмем их как начальные и пойдем вверх. <br>Таким образом все рёбра будут покрыты. 2. # Все пути не пересекаются. <br>Докажем от противного. Пусть мы взяли какое-то ребро дважды. Это значит, что из какой-то вершины вело более чем одно тяжёлое ребро, чего быть не могло. Получили противоречие. 3. # При прохождении пути от вершины <tex>v</tex> до вершины <tex>u</tex> произойдет смена не более, чем <tex>O(\log{n})</tex> путей. <br>Докажем эквивалентный факт, что при пути от любой вершины до корня мы сменим не более, чем <tex>O(\log{n})</tex> путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в 2 раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более <tex>O(\log{n})</tex> путей.

==СсылкиИсточники информации==