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

Heavy-light декомпозиция — техника разбиения подвешенного дерева на множество путей для решения задач о запросах на пути в дереве (в том числе с модификациями).

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

Задача:

Имеется подвешенное дерево [math]T[/math] c [math]n[/math] вершинами и необходимо проводить операции на нем на пути от вершины [math]v[/math] до вершины [math]u[/math].

Примеры запросов:

• сумма на пути,
• максимум на пути,
• количество рёбер на пути, вес которых больше заданного [math]c[/math].

Примеры модификаций:

• модификация одного ребра,
• прибавление к весу всех рёбер на пути,
• установка веса всех рёбер на пути в заданное [math]c[/math].

Множество подобных запросов делаются за время за полином от логарифма (обычно [math]O(\log^2{n})[/math]) с помощью heavy-light декомпозиции.

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

Пример разбиения. В вершинах указан размер поддерева.

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

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

Тяжёлые ребра (англ. heavy edge) — ребра [math](u, v)[/math] такие, что [math]s(v) \geqslant[/math] [math]\dfrac{s(u)}{2}[/math].

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

Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум [math]\dfrac{s(u)}{2}[/math] вершин, а также сама вершина [math]u[/math]. Итого [math]s(u) + 1[/math] вершин, тогда как у нас всего [math]s(u)[/math] вершин в поддереве.

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Существует вариант heavy-light декомпозиции на вершинно-непересекающихся путях. Чтобы получить такой путь нужно всего-лишь выкинуть последнее ребро из всех путей в рёберно-непересекающейся декомпозиции. Это может быть удобно при решении задач, где веса находятся не на рёбрах, а на вершинах и соответствующие запросы также делаются на вершинах.

Применение

Сумма на пути

Классическая задача о сумме на пути в дереве с [math]n[/math] вершинами может быть решена с помощью heavy-light декомпозиции за время [math]O(\log^2{n})[/math]. Возможны модификации веса.

Построим дерево отрезков над каждым путём. Рассмотрим запрос [math]sum(u, v)[/math]. Найдем вершину [math]c[/math], которая является [math]\mathrm{LCA}(u, v)[/math] (например с помощью двоичного подъема. Мы разбили запрос на два: [math](u, c)[/math] и [math](c, v)[/math], на каждый из которых можно легко ответить разбив его на множество путей из декомпозиции и ответив на каждый путь из этого множества по отдельности за [math]O(\log{n})[/math] с помощью дерева отрезков на этом пути. Всего таких путей нужно будет рассмотреть [math]O(\log{n})[/math]. Итого мы способны решить эту задачу за время [math]O(\log^2{n})[/math].

Хоть это и не самый эффективный способ для решения этой задачи, но можно заметить, что навесив дерево отрезков на каждый путь мы способны отвечать на любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на моноиде (операции, поддерживаемые деревом отрезков), такие как: сумма на пути, максимум на пути, количество рёбер на пути, удовлетворяющих какому-то свойству.

LCA

Задача о наименьшем общем предке для двух вершин в дереве с [math]n[/math] вершинами также может быть решена с помощью heavy-light декомпозиции. Воспользуемся основной идеей: декомпозиция разбивает все вершины дерева на реберно-непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более [math]\log{n}[/math] различных путей.

Лемма:

Пусть есть вершины [math]u[/math] и [math]v[/math], лежащие на разных путях. При этом [math]U[/math], [math]V[/math] — корни путей, на которых они лежат. Если [math]U[/math] более удален от корня, чем [math]V[/math], то [math]\mathrm{LCA}(u, v) = \mathrm{LCA}(U, v)[/math].

Доказательство:

[math]\triangleright[/math]

Допустим, пути не пересекаются. Предположим, что [math]\mathrm{LCA}[/math] не равны. Тогда существует вершина, на пути от [math]u[/math] к [math]U[/math], являющаяся [math]\mathrm{LCA}[/math]. Значит [math]\mathrm{LCA}[/math] должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию. Теперь рассмотрим случай, когда пути пересекаются. Пути не могут совпадать более, чем в одной вершине, так как построенная декомпозиция является реберно-непересекающейся. При этом корень одного из путей является вершиной другого (либо корни совпадают, что равносильно), поскольку в противном случае пути пересекаются в более чем [math]1[/math] вершине, что противоречит предыдущему условию. [math]\mathrm{LCA}[/math] должен принадлежать двум путям, значит именно этот корень и будет [math]\mathrm{LCA}[/math].

[math]\triangleleft[/math]

Препроцессинг

Построим heavy-light декомпозицию для данного нам дерева. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:

1. Расстояние до корня дерева.
   Вычисляется за [math]O(1)[/math] с помощью времен входа\выхода в каждую вершину.
2. Корень пути, на котором лежит вершина.
   Поскольку вершина может принадлежать нескольким путям, выберем тот, чья начальная вершина наиболее удалена от корня дерева. Имея разбиение на пути, найти корень можно за [math]O(1)[/math].
3. Вторая вершина этого пути.
   Аналогично, находится за [math]O(1)[/math] при построении.

Вычисление LCA

Найдем [math]\mathrm{LCA}[/math] для двух вершин. Для этого будем рекурсивно подниматься от этих вершин в направлении корня. Пусть на данной итерации рассматриваем вершины [math]u[/math] и [math]v[/math]. Заметим, что если эти вершины лежат на одном пути, то ответ — это такая вершина ([math]u[/math] или [math]v[/math]), которая находится ближе к корню. Очевидно, что если расстояние от корня до [math]u[/math] меньше, чем расстояние до [math]v[/math], то [math]u[/math] является предком [math]v[/math]. Иначе, наоборот.

Для проверки этого условия недостаточно знать только корни путей, потому что несколько путей могу иметь общий корень. Но любые два пути пересекаются не более чем в одной вершине. Воспользуемся этим фактом.

Пусть [math]a[/math] и [math]b[/math] — вторые вершины путей, содержащих вершины [math]u[/math] и [math]v[/math] соответственно. Важно заметить, что любая вершина, помимо корня дерева является некорневой вершиной какого-либо другого пути, поэтому такие [math]a[/math] и [math]b[/math] всегда существуют.

• Заметим, что если [math]a[/math] = [math]b[/math], то [math]u[/math] и [math]v[/math] лежат на одном пути. Этот случай мы уже рассмотрели ранее.

• Если это не так, то вершины лежат на разных путях. По лемме, так как пути реберно не пересекаются, то ответ не изменится, если вместо одной из вершин взять корень того пути, на котором она лежит. Эту операцию будем производить с той вершиной, чей предок наиболее удален от корня. Рекурсивно запустимся от выбранной и оставшейся вершин.

Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем [math]\mathrm{LCA}[/math].

Псевдокод

Объявим несколько массивов для хранения дополнительной информации:

• [math]\mathtt{dist}[/math] — расстояние от корня до вершины.
• [math]\mathtt{last}[/math] — начало пути, на котором лежит вершина. Из всех путей выбирается путь с самой удаленной от корня дерева начальной вершины.
• [math]\mathtt{turn}[/math] — вторая вершина этого пути.

Ниже представлен псевдокод функции получения наименьшего общего предка:

 // Находит наименьшего общего предка вершин [math]u[/math] и [math]v[/math]
 int lca(int u, int v):
   // Проверяем вторые вершины путей, содержащих [math]u[/math] и [math]v[/math].
   if (turn[u] == turn[v]):
     // Ответ найден, выберем ближайшую к корню.
     if (dist[u] < dist[v]):
       return u
     else:
       return v
    
   // Рекурсивно запустимся от вершины, чей предок наиболее удален от корня.
   if (dist[last[u]] > dist[last[v]]):
     return lca(last[u], v)
   return lca(last[v], u)

Асимптотика

• Память: для реализации алгоритма требуется [math]O(n)[/math] памяти.
• Препроцессинг: heavy-light декомпозиция строится за [math]O(n)[/math], вся дополнительная информация считается за [math]O(1)[/math] для каждой из вершин.
• Запросы: по свойству heavy-light декомпозиции, на пути от вершины к корню мы сменим не более [math]\log n[/math] путей. Значит время выполнения запроса также [math]O(\log n)[/math].

Реализация

Ниже будет приведена реализация запроса сумма на пути между любыми двумя вершинами в дереве без запросов модификации. Все запросы, сводящиеся к навешиванию дерева отрезков на пути из декомпозиции делаются похожим образом.

Опущены некоторые детали реализации: построение и дерево отрезков.

• [math]\mathrm{pathPos}[/math] — функция, позволяющая найти смещение вершины в пути относительно корня пути,
• [math]\mathrm{getValue(\mathtt{i}, \mathtt{j})}[/math] — функция, позволяющая найти вес [math]\mathtt{j}[/math]-ого ребра в [math]\mathtt{i}[/math]-ом пути.

Пример реализации запроса суммы на пути:

int query(int u, int v):
    int res = 0
    int root = корень пути, в котором находится u
    while root не является предком v      // поднимаемся до тех пор, пока наш путь не содержит общего предка u и v
        segmentTree = дерево отрезков, соответствующее пути, в котором лежит u
        res += segmentTree.sum(0, pathPos(u))
        u = предок root                   // вырезали нижний путь и подняли нижнюю вершину до нижней вершины следующего пути
        root = корень пути, в котором находится u
    
    root = корень пути, в котором находится v
    while root не является предком u      // аналогично прошлому while, но с другой стороны
        segmentTree = дерево отрезков, соответствующее пути, в котором лежит v
        res += segmentTree.sum(0, pathPos(v))
        v = предок root
        root = корень пути, в котором находится v
    
    // последний путь (тот, что содержит общего предка) обрезан с двух сторон полученными вершинами
    segmentTree = дерево отрезков, соответствующее пути в котором лежит u
    res += segmentTree.sum(min(pathPos(u), pathPos(v)), max(pathPos(u), pathPos(v)))
    return res

См.также

• Метод двоичного подъема
• Дерево отрезков. Построение
• Link-Cut Tree

Источники информации

• Wikipedia — Heavy path decomposition
• MAXimal :: algo :: Heavy-light декомпозиция
• Habrahabr — Алгоритм поиска наименьшего общего предка в дереве