Изменения

Перейти к: навигация, поиск

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

1001 байт добавлено, 19:27, 4 сентября 2022
м
rollbackEdits.php mass rollback
</ul>
Множество подобных запросов делаются за время за полином от логарифма (обычно <tex>O(\log^2{n})</tex>) с помощью Heavyheavy-light декомпозиции.
==Описание декомпозиции==
[[Файл:Heavylight.png|thumb|right|800x280px|Пример разбиения. В вершинах указан размер поддерева.]]
Необходимо составить такую декомпозицию дерева на множество рёберно-непересекающихся путей, что при прохождении от одной вершины до другой произойдет смена не более <tex>O(\log{n})</tex> путей из декомпозиции.
Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в <tex>2 </tex> вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>.
'''Тяжёлые ребра''' (англ. ''heavy edge'') {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geqslant</tex> <tex dpi="150">\fracdfrac{s(u)}{2}</tex>.
'''Лёгкие ребра''' (англ. ''light edge'') {{---}} соответственно все остальные.
Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум <tex dpi="150">\fracdfrac{s(u)}{2}</tex> вершин, а также сама вершина <tex>u</tex>. Итого <tex>s(u) + 1</tex> вершин, тогда как у нас всего <tex>s(u)</tex> вершин в поддереве.
Теперь рассмотрим вершины, из которых не ведет вниз ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что полученная таким образом декомпозиция будет являться искомой и корректной.
Докажем по отдельности корректность декомпозиции.
# Все рёбра покрыты путями. <br>Есть два типа вершин: те, из которых ведёт ровно одно тяжёлое ребро и те, из которых не ведёт ни одного тяжёлого ребра. Для первого типа вершин мы дойдем до них некоторым путём через тяжёлое ребро снизу по определению выбора путей, а лёгкие рёбра ведущие из неё возьмем как последние рёбра в соответствующих путях. Для второго типа вершин мы по определению выбора путей возьмем их как начальные и пойдем вверх. <br>Таким образом все рёбра будут покрыты.
# Все пути не пересекаются. <br>Докажем от противного. Пусть мы взяли какое-то ребро дважды. Это значит, что из какой-то вершины вело <tex>v</tex> ведет более чем одно тяжёлое <tex>1</tex> тяжелого ребра в детей. Эти ребра относятся к разным путями, однако пути имеют хотя бы общее ребро {{---}} реброиз <tex>v</tex> в отца <tex>v</tex>. Более <tex>1</tex> тяжелого ребра из вершины идти не может, следовательно, чего быть не могло. Получили получили противоречие.# При прохождении пути от вершины <tex>v</tex> до вершины <tex>u</tex> произойдет смена не более, чем <tex>O(\log{n})</tex> путей. <br>Докажем эквивалентный факт, что при пути от любой вершины до корня мы сменим не более, чем <tex>O(\log{n})</tex> путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в <tex>2 </tex> раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более <tex>O(\log{n})</tex> путей.
}}
Существует вариант Heavyheavy-light декомпозиции на вершинно-непересекающихся путях. Чтобы получить такой путь нужно всего-лишь выкинуть последнее ребро из всех путей в рёберно-непересекающейся декомпозиции. Это может быть удобно при решении задач, где веса находятся не на рёбрах, а на вершинах и соответствующие запросы также делаются на вершинах.
==Применение==
===Сумма на пути===
Классическая задача о сумме на пути в дереве с <tex>n</tex> вершинами решается может быть решена с помощью Heavyheavy-light декомпозиции за время <tex>O(\log^2{n})</tex>. Возможны модификации веса.
Построим [[Дерево отрезков. Построение|дерево отрезков]] над каждым путём. Рассмотрим запрос <tex>sum(u, v)</tex>. Найдем вершину <tex>c</tex>, которая является <tex>\mathrm{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>\mathrm{LCA}(au, bv) </tex> = <tex>\mathrm{LCA}(AU, Bv)</tex>.
|proof=Пусть Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}(u, v)</tex> и <tex>\mathrm{LCA не равны}(U, v)</tex> это разные вершины. Значит Тогда существует вершина, на пути от <tex>au</tex> к <tex>AU</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Но Значит <tex>\mathrm{LCA }</tex> должен принадлежать двум путям. Но , но по предположению пути на не пересекаются. Тем самым пришли к противоречию.
Рассмотрим Теперь рассмотрим случай, когда пути пересекаются. Пути не могут пересекайся совпадать более, чем в одной вершине, так как построенная декомпозиция является реберно-непересекающейся. В данном случае При этом корень одного из путей является вершиной другого(либо корни совпадают, что равносильно), поскольку в противном случае пути пересекаются в более чем <tex>1</tex> вершине, что противоречит предыдущему условию. <tex>\mathrm{LCA }</tex> должен принадлежать двум путям, значит именно этот корень и будет <tex>\mathrm{LCA}</tex>.
}}
====Препроцессинг====
Построим heavy-light декомпозициюданного нам дерева. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:
# Расстояние до корня дерева. <br />Вычисляется за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину.
# Корень пути, на котором лежит текущая вершина. <br />Из всех путей выбираем Поскольку вершина может принадлежать нескольким путям, выберем тот, чья начальная вершина наиболее удалена от корня дерева. Очевидно, что имея Имея разбиение на пути, найти корень можно за <tex>O(1)</tex>.
# Вторая вершина этого пути. <br />Аналогично, находится за <tex>O(1)</tex> при построении.
====Вычисление LCA====
Пусть требуется найти Найдем <tex>\mathrm{LCA }</tex> для двух вершин. Для этого будем рекурсивно подниматься от этих вершин в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, и <tex>v</tex>. Заметим, что если эти вершины лежат на одном пути, то мы нашли ответ: LCA будет та{{---}} это такая вершина (<tex>u</tex> или <tex>v</tex>), которая находится ближе к корню, т.е расстояние от корня до которой минимально. Очевидно, что если расстояние от корня до <tex>u</tex> до корня меньше, чем расстояние от до <tex>v</tex> до корня, то <tex>u</tex> является предком <tex>bv</tex>. Иначе, а не наоборот.
Для проверки этого условия недостаточно знать только корни путей. Потому , потому что бесконечно большое количество несколько путей могу иметь общий корень. Но любые два пути пересекаются не более чем в одной вершине. Воспользуемся этим фактом.
Пусть <tex>a</tex> и <tex>b</tex> {{---}} вторые вершины путей, содержащих вершины <tex>u</tex> и <tex>v</tex> соответственно. Важно заметить, что любая вершина, помимо корня дерева является некорневой вершиной какого-либо другого пути, поэтому такие <tex>a</tex> и <tex>b</tex> всегда существуют.
* Заметим, что если <tex>a</tex> = <tex>b</tex>, то или <tex>u</tex> лежит на пути от корня к и <tex>v</tex>, или наоборотлежат на одном пути. Этот случай мы уже рассмотрели ранее.
* Если это не так, то вершины лежат на разных путях. По лемме, т.к так как пути реберно не пересекаются, то ответ не изменится, если вместо одной из вершин взять корень того пути, на котором она лежит. Эту операцию будем производить с той вершиной, чей предок наиболее удален от корня. Рекурсивно запустимся от выбранной и оставшейся вершин.
 Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем <tex>\mathrm{LCA}</tex>.
====Псевдокод====
Ниже представлен псевдокод функции получения наименьшего общего предка:
<code>
<font color=darkgreen>// Находит наименьшего общего предка вершин <tex>u</tex> и <tex>v</tex></font>
'''int''' lca('''int''' u, '''int''' v):
<font color=darkgreen>// Проверяем вторые вершины путей, содержащих <tex>u</tex> и <tex>v</tex>.</font>
'''if''' (turn[u] == turn[v]):
<font color=darkgreen>// Ответ найден, выберем ближайшую к корню.</font>
'''if''' (dist[u] < dist[v]):
'''return''' u
'''else''':
'''return''' v
<font color=darkgreen>// Рекурсивно запустимся от вершины, чей предок наиболее удален от корнядерева.</font> '''if''' (dist[last[u]] > dist[last[v]]):
'''return''' lca(last[u], v)
'''return''' lca(last[v], u)
</code>
====АссимптотикаАсимптотика====
* '''Память''': для реализации алгоритма требуется <tex>O(n)</tex> памяти.
* '''Препроцессинг''': heavy-light декомпозиция строится за <tex>O(n)</tex>, вся дополнительная информация считается за <tex>O(1)</tex> для каждой из вершин.
</ul>
Пример реализации запроса суммы на пути:
<code> '''int''' query('''int''' u, '''int''' v):
'''int''' res = 0
'''int''' root = корень пути, в котором находится u
'''while''' root не является предком v <font color=green> // поднимаемся до тех пор, пока наш путь не содержит общего предка u и v</font>
segmentTree = дерево отрезков, соответствующее пути, в котором лежит u
res += segmentTree.sum(0, pathPos(u))
u = предок root <font color=green> // вырезали нижний путь и подняли нижнюю вершину до нижней вершины следующего пути</font>
root = корень пути, в котором находится u
root = корень пути, в котором находится v
'''while''' root не является предком u <font color=green> // аналогично прошлому while, но с другой стороны</font>
segmentTree = дерево отрезков, соответствующее пути, в котором лежит v
res += segmentTree.sum(0, pathPos(v))
v = предок root
root = корень пути, в котором находится v
<font color=green>// последний путь (тот, что содержит общего предка) обрезан с двух сторон полученными вершинами</font>
segmentTree = дерево отрезков, соответствующее пути в котором лежит u
res += segmentTree.sum(min(pathPos(u), pathPos(v)), max(pathPos(u), pathPos(v)))
'''return''' res
</code>
== См.также ==
1632
правки

Навигация