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] в 2 вида: легкие и тяжёлые. Введём функцию [math]s(v)[/math], которая будет обозначать размер поддерева вершины [math]v[/math].

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

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

Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум [math]\frac{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] путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в 2 раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более [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]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]O(\log{n})[/math].

Мы можем проверять, что вершина является предком другой вершины за [math]O(1)[/math] с помощью времен входа\выхода в каждую вершину. Тогда рассмотрим самый нижний путь (содержащий первую вершину) и посмотрим на его корень (самая высокая вершина в пути). Если эта вершина является предком второй вершины, то ответ где-то в этом пути, иначе выкинем этот путь и рассмотрим следующий вверх за ним.

Когда мы определили путь, в котором содержится ответ, мы можем с помощью бинпоиска найти в нём первую вершину, являющуюся предком второй вершины. Эта вершина является ответом.

Итого мы рассмотрели корень каждого пути за [math]O(1)[/math], а путей всего [math]O(\log{n})[/math]. И в последнем пути один раз запустили бинпоиск, который отработал за [math]O(\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 декомпозиция