Heavy-light декомпозиция

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

Описание задачи

Пусть у нас есть дерево [math]T[/math] c [math]n[/math] вершинами и нам нужно проводить операции на нем на пути от вершины [math]v[/math] до вершины [math]u[/math]. Множество подобных запросов делаются за время [math]O(\log{n})[/math] при Heavy-light декомпозиции.

Описание декомпозиции

Декомпозиция заключается в классификации всех рёбер дерева [math]T[/math] в 2 вида: легкие и тяжёлые. Введём функцию [math]s(v)[/math], которая будет обозначать размер поддерева вершины [math]v[/math]

Тяжёлые ребра — ребра [math](u, v)[/math] такие, что [math]s(v) \geq s(u) / 2[/math].

Лёгкие ребра — соответственно все остальные.

Теперь рассмотрим вершины, из которых не ведет ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что оно будет являться искомым.

Доказательство корректности полученной декомпозиции

Утверждение:

Полученная декомпозиция является искомой.

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Примеры задач

Some examples