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

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

int queryPath(int path, int from, int to):
    int res = 0
    while from <= to:
        if from mod 2 == 1:
            res += getValue(path, from)
        if to mod 2 == 0:
            res += getValue(path, to)
        to = (to - 1) / 2
        from = (from + 1) / 2
    return res

int query(int u, int v):
    int res = 0
    int root = pathRoot(u)
    while not (root is ancestor of v) // поднимаемся до тех пор, пока наш путь не содержит общего предка u и v
        res += queryPath(getPath(u), 0, pathPos(u))
        u = parent of root            // вырезали нижний путь и подняли нижнюю вершину до нижней вершины следующего пути
        root = pathRoot(u)
    root = pathRoot(v)
    while not (root is ancestor of u) // аналогично прошлому while, но с другой стороны
        res += queryPath(getPath(v), 0, pathPos(v))
        v = parent of root
        root = pathRoot(v)
    // последний путь (тот, что содержит общего предка) обрезан с двух сторон полученными вершинами
    res += queryPath(path(u), min(pathPos(u), pathPos(v)), max(pathPos(u), pathPos(v)))
    return res

См.также

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

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

• Wikipedia — Heavy path decomposition
• MAXimal :: algo :: Heavy-light декомпозиция