http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=91.122.56.202&*Викиконспекты - Вклад участника [ru]2026-06-13T01:46:39ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=Heavy-light_%D0%B4%D0%B5%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D1%8F&diff=47531Heavy-light декомпозиция2015-06-05T07:19:23Z<p>91.122.56.202: </p>
<hr />
<div>'''Heavy-light декомпозиция''' {{---}} техника разбиения дерева на множество рёберно-непересекающихся путей так, чтобы при прохождении от одной вершины до другой произошла смена не более, чем <tex>O(\log{n})</tex> путей.<br />
==Описание задачи==<br />
Пусть у нас есть дерево <tex>T</tex> c <tex>n</tex> вершинами и нам нужно проводить операции на нем на пути от вершины <tex>v</tex> до вершины <tex>u</tex>. Множество подобных запросов делаются за время <tex>O(\log^p{n})</tex> при Heavy-light декомпозиции.<br />
==Описание декомпозиции==<br />
Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в 2 вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex><br />
<br />
'''Тяжёлые ребра''' {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geq s(u) / 2</tex>.<br />
<br />
'''Лёгкие ребра''' {{---}} соответственно все остальные.<br />
<br />
Теперь рассмотрим вершины, из которых не ведет ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что оно будет являться искомым.<br />
==Доказательство корректности полученной декомпозиции==<br />
{{Утверждение<br />
|statement = Полученная декомпозиция является искомой.<br />
|proof =<br />
Докажем по отдельности корректность декомпозиции.<br />
<br />
1. Все рёбра покрыты путями.<br />
<br />
Есть два типа вершин: те, из которых ведёт ровно одно тяжёлое ребро и те, из которых не ведёт ни одного тяжёлого ребра. Для первого типа вершин мы дойдем до них некоторым путём через тяжёлое ребро снизу по определению выбора путей, а лёгкие рёбра ведущие из неё возьмем как последние рёбра в соответствующих путях. Для второго типа вершин мы по определению выбора путей возьмем их как начальные и пойдем вверх.<br />
<br />
Таким образом все рёбра будут покрыты.<br />
<br />
2. Все пути не пересекаются.<br />
<br />
Докажем от противного. Пусть мы взяли какое-то ребро дважды. Это значит, что из какой-то вершины вело более чем одно тяжёлое ребро, чего быть не могло. Получили противоречие.<br />
<br />
3. При прохождении пути от вершины <tex>v</tex> до вершины <tex>u</tex> произойдет смена не более, чем <tex>O(\log{n})</tex> путей.<br />
<br />
Докажем эквивалентный факт, что при пути от любой вершины до корня мы сменим не более, чем <tex>O(\log{n})</tex> путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в 2 раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более <tex>O(\log{n})</tex> путей.<br />
}}<br />
<br />
==Примеры задач==<br />
Some examples</div>91.122.56.202http://neerc.ifmo.ru/wiki/index.php?title=Heavy-light_%D0%B4%D0%B5%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D1%8F&diff=47465Heavy-light декомпозиция2015-06-04T17:57:55Z<p>91.122.56.202: </p>
<hr />
<div>'''Heavy-light декомпозиция''' {{---}} техника разбиения дерева на множество рёберно-непересекающихся путей так, чтобы при прохождении от одной вершины до другой произошла смена не более, чем <tex>O(\log{n})</tex> путей.<br />
==Описание задачи==<br />
Пусть у нас есть дерево <tex>T</tex> c <tex>n</tex> вершинами и нам нужно проводить операции на нем на пути от вершины <tex>v</tex> до вершины <tex>u</tex>. Множество подобных запросов делаются за время <tex>O(\log{n})</tex> при Heavy-light декомпозиции.<br />
==Описание декомпозиции==<br />
Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в 2 вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex><br />
<br />
'''Тяжёлые ребра''' {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geq s(u) / 2</tex>.<br />
<br />
'''Лёгкие ребра''' {{---}} соответственно все остальные.<br />
<br />
Теперь рассмотрим вершины, из которых не ведет ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что оно будет являться искомым.<br />
==Доказательство корректности полученной декомпозиции==<br />
{{Утверждение<br />
|statement = Полученная декомпозиция является искомой.<br />
|proof =<br />
Докажем по отдельности корректность декомпозиции.<br />
<br />
1. Все рёбра покрыты путями.<br />
<br />
Есть два типа вершин: те, из которых ведёт ровно одно тяжёлое ребро и те, из которых не ведёт ни одного тяжёлого ребра. Для первого типа вершин мы дойдем до них некоторым путём через тяжёлое ребро снизу по определению выбора путей, а лёгкие рёбра ведущие из неё возьмем как последние рёбра в соответствующих путях. Для второго типа вершин мы по определению выбора путей возьмем их как начальные и пойдем вверх.<br />
<br />
Таким образом все рёбра будут покрыты.<br />
<br />
2. Все пути не пересекаются.<br />
<br />
Докажем от противного. Пусть мы взяли какое-то ребро дважды. Это значит, что из какой-то вершины вело более чем одно тяжёлое ребро, чего быть не могло. Получили противоречие.<br />
<br />
3. При прохождении пути от вершины <tex>v</tex> до вершины <tex>u</tex> произойдет смена не более, чем <tex>O(\log{n})</tex> путей.<br />
<br />
Докажем эквивалентный факт, что при пути от любой вершины до корня мы сменим не более, чем <tex>O(\log{n})</tex> путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в 2 раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более <tex>O(\log{n})</tex> путей.<br />
}}<br />
<br />
==Примеры задач==<br />
Some examples</div>91.122.56.202