Тяжело-легкая декомпозиция — это довольно общий метод, который позволяет нам эффективно решать многие проблемы, сводящиеся к запросам к дереву.
Описание
Пусть имеется дерево G из n вершин с произвольным корнем.
Пример проблемы: давайте разберемся с разложением тяжелого-легкого (HLD) с помощью приведенного ниже примера.
Предположим, у нас есть несбалансированное дерево (не обязательно бинарное дерево) из n узлов, и нам нужно выполнить операции над деревом, чтобы ответить на ряд запросов, каждый из которых может быть одного из двух типов:
- change(a, b): обновить вес ребра ath до b.
- maxEdge(a, b): вывести максимальный вес ребра на пути от узла a к узлу b. Например, maxEdge(5, 10) должен напечатать 25.
Предположим, что узлы пронумерованы от 1 до n. Должно быть n-1 ребер. Веса ребер являются натуральными числами. Также предположим, что оба типа запросов перемежаются (примерно равное количество), и, следовательно, ни один из типов не может быть отодвинут на второй план, чтобы снизить сложность.
Простое решение. Простое решение — пройтись по всему дереву для любого запроса. Временная сложность каждого запроса в этом решении составляет O(n).
Решение на основе HLD.
При внимательном рассмотрении двух операций мы понимаем, что где-то их видели. Эврика! Сегментные деревья. Дерево сегментов можно использовать для выполнения обоих типов за O (log (n)). Но ждать! Дерево сегментов может быть построено из одномерного массива/цепочки (набор узлов, соединенных один за другим), и здесь мы имеем дерево. Итак, можем ли мы свести дерево к цепочкам?
Решение на основе HLD, обсуждаемое в посте, требует O(log2(n)) для maxEdge() и O(log n) для change().
Размер узла x — это количество узлов в поддереве, корнем которого является узел x. Вот изображение, показывающее размеры поддеревьев каждого узла, написанного поверх них:
ДВУ корневого дерева – это метод разбиения вершин дерева на непересекающиеся цепочки (две цепочки не имеют общего узла) для достижения важных асимптотических временных ограничений для некоторых задач, связанных с деревьями.
HLD также можно рассматривать как «окрашивание» ребер дерева. «Heavy-Light» возникает из-за того, как мы разделяем ребра. В качестве критерия мы используем размер поддеревьев с корнями в узлах.
Ребро является тяжелым, если size(v) › size(u), где u — любой из братьев и сестер v. Если они оказываются равными, мы выбираем любое такое v как особенное.
операция change(u, v):
Поскольку дерево сегментов используется в качестве базовой структуры данных для представления отдельных цепочек, изменение выполняется с помощью обновления дерева сегментов. Таким образом, операция временная сложность изменения равна O(Log n).
Операция maxEdge(u, v):
- Сначала мы находим LCA двух узлов. Скажем, узел u равен 11, а узел v равен 9. Их LCA — это узел 1.
- Затем мы ползаем вверх по дереву от узла u до lca. Если узел u и lca принадлежат одной и той же цепочке, мы находим максимум из диапазона, который представляет ребра между ними, используя дерево сегментов. В противном случае мы находим максимум из цепочки, к которой принадлежит u, затем меняем цепочки и повторяем, пока мы не находимся в той же цепочке.
- Мы повторяем тот же шаг (как шаг 2) от v до lca и возвращаем максимум два веса.
Как и в нашем примере выше, давайте возьмем u в качестве узла 11 и v в качестве узла 9. LCA — это узел 1. Мы переходим от узла 11 к узлу 1 и меняем цепочки один раз. Когда мы меняем цепочки, мы переходим от нашего запрошенного узла к родителю главы цепочки, которой он принадлежит (здесь 11 меняется на 8). Точно так же был запрошен узел 9-3 (включая светлый край), и цепочка изменилась (узел изменился на 1).
Временная сложность maxEdge – O(log2(n)). Запрос максимума цепочки занимает O(log(n)) времени, так как цепочки представлены с использованием дерева сегментов, и существует не более O(log(n)) цепочек.
Какое количество цепочек O(log(n))?
Все цепочки соединены светлым ребром (см. примеры выше). Таким образом, количество цепей ограничено количеством светлых ребер на любом пути. Если идти по светлому ребру от корня, то поддерево с корнем в результирующей вершине будет иметь размер не более n/2. Если мы повторим, то попадем в вершину с размером поддерева не более n/4 и так далее. Мы заключаем, что количество светлых ребер на любом пути от корня к листу не превосходит log(n).
Основная идея тяжелой облегченной декомпозиции несбалансированного дерева состоит в том, чтобы объединить вершины длинных (или тяжелых) путей в цепочки, чтобы эти линейные цепочки можно было запрашивать за время O (Log n) с использованием структуры данных, такой как дерево сегментов.
