102
правки
Изменения
Новая страница: «'''Heavy-light декомпозиция''' {{---}} техника разбиения дерева на множество рёберно-непересекающ...»
'''Heavy-light декомпозиция''' {{---}} техника разбиения дерева на множество рёберно-непересекающихся путей так, чтобы при прохождении от одной вершины до другой произошла смена не более, чем <tex>O(\log{n})</tex> путей.
==Описание задачи==
Пусть у нас есть дерево <tex>T</tex> c <tex>n</tex> вершинами и нам нужно проводить операции на нем на пути от вершины <tex>v</tex> до вершины <tex>u</tex>. Множество подобных запросов делаются за время <tex>O(\log{n})</tex> при Heavy-light декомпозиции.
==Описание декомпозиции==
Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в 2 вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>
'''Тяжёлые ребра''' {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geq s(u) / 2</tex>.
'''Лёгкие ребра''' {{---}} соответственно все остальные.
Теперь рассмотрим вершины, из которых не ведет ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что оно будет являться искомым.
==Доказательство корректности полученной декомпозиции==
Ну там понятно вроде
==Примеры задач==
Some examples
==Описание задачи==
Пусть у нас есть дерево <tex>T</tex> c <tex>n</tex> вершинами и нам нужно проводить операции на нем на пути от вершины <tex>v</tex> до вершины <tex>u</tex>. Множество подобных запросов делаются за время <tex>O(\log{n})</tex> при Heavy-light декомпозиции.
==Описание декомпозиции==
Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в 2 вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>
'''Тяжёлые ребра''' {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geq s(u) / 2</tex>.
'''Лёгкие ребра''' {{---}} соответственно все остальные.
Теперь рассмотрим вершины, из которых не ведет ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что оно будет являться искомым.
==Доказательство корректности полученной декомпозиции==
Ну там понятно вроде
==Примеры задач==
Some examples
