Heavy-light декомпозиция
Heavy-light декомпозиция — техника разбиения подвешенного дерева на множество путей для решения задач о запросах на пути в дереве (в том числе с модификациями).
Описание задачи
Задача: |
Имеется подвешенное дерево | c вершинами и необходимо проводить операции на нем на пути от вершины до вершины .
Примеры запросов:
- сумма на пути,
- максимум на пути,
- количество рёбер на пути, вес которых больше заданного .
Примеры модификаций:
- модификация одного ребра,
- прибавление к весу всех рёбер на пути,
- установка веса всех рёбер на пути в заданное .
Множество подобных запросов делаются за время за полином от логарифма (обычно
) с помощью Heavy-light декомпозиции.Описание декомпозиции
Необходимо составить такую декомпозицию дерева на множество рёберно-непересекающихся путей, что при прохождении от одной вершины до другой произойдет смена не более
путей из декомпозиции.Декомпозиция заключается в классификации всех рёбер дерева
в 2 вида: легкие и тяжёлые. Введём функцию , которая будет обозначать размер поддерева вершины .Тяжёлые ребра (англ. heavy edge) — ребра
такие, что .Лёгкие ребра (англ. light edge) — соответственно все остальные.
Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум
вершин, а также сама вершина . Итого вершин, тогда как у нас всего вершин в поддереве.Теперь рассмотрим вершины, из которых не ведет вниз ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что полученная таким образом декомпозиция будет являться искомой и корректной.
Утверждение: |
Полученная декомпозиция является искомой. |
Докажем по отдельности корректность декомпозиции.
|
Существует вариант Heavy-light декомпозиции на вершинно-непересекающихся путях. Чтобы получить такой путь нужно всего-лишь выкинуть последнее ребро из всех путей в рёберно-непересекающейся декомпозиции. Это может быть удобно при решении задач, где веса находятся не на рёбрах, а на вершинах и соответствующие запросы также делаются на вершинах.
Применение
Сумма на пути
Классическая задача о сумме на пути в дереве с
вершинами решается с помощью Heavy-light декомпозиции за время . Возможны модификации веса.Построим дерево отрезков над каждым путём. Рассмотрим запрос . Найдем вершину , которая является (например с помощью двоичного подъема. Мы разбили запрос на два: и , на каждый из которых можно легко ответить разбив его на множество путей из декомпозиции и ответив на каждый путь из этого множества по отдельности за с помощью дерева отрезков на этом пути. Всего таких путей нужно будет рассмотреть . Итого мы способны решить эту задачу за время .
Хоть это и не самый эффективный способ для решения этой задачи, но можно заметить, что навесив дерево отрезков на каждый путь мы способны отвечать на любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на моноиде (операции, поддерживаемые деревом отрезков), такие как: сумма на пути, максимум на пути, количество рёбер на пути, удовлетворяющих какому-то свойству.
LCA
Задача о наименьшем общем предке для двух вершин в дереве с
вершинами решается с помощью heavy-light декомпозиции. Воспользуемся основной идеей: декомпозиция разбивает все вершины дерева на вершинно-непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более различных путей.Препроцессинг
Построим декомпозицию. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:
- Расстояние до корня дерева.
Вычисляется за с помощью времен входа\выхода в каждую вершину. - Номер корня текущего пути.
Очевидно, что имея разбиение на пути, найти корень можно за . - Вторая вершина текущего пути.
Аналогично, находится за при построении.
Вычисление LCA
Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины
, .Пусть вершина
— первая вершина пути из предка вершины в вершину , а — первая вершина пути из предка вершины в вершину .- Заметим, что если = , то или лежит на пути от корня к , или наоборот. За LCA примем ту вершину, которая лежит ближе к корню, т.е расстояние от корня до которой минимально. Очевидно, что если расстояние от до корня меньше, чем расстояние от до корня, то является предком , а не наоборот.
- Иначе, вершины лежат на разных путях — ответ не изменится, если вместо одной из вершин взять корень того пути, на котором она лежит. Эту операцию будем производить с той вершиной, чей предок наименее удален от корня. Рекурсивно запустимся от выбранной и оставшейся вершин.
Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем LCA.
Псевдокод
Объявим несколько массивов, для хранения дополнительной информации:
- dist — расстояние от корня до вершины.
- last — начало пути, на котором лежит вершина.
- turn — вторая вершина этого пути.
Тогда запрос на нахождение LCA будет иметь вид:
// Находит наименьшего общего предка вершини int lca(int u, int v): // Проверяем вершины, в которые идут ребра из предков. 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)
Ассимптотика
- Память: Для реализации алгоритма требуется памяти.
- Препроцессинг: heavy-light декомпозиция строится за , вся дополнительная информация считается за для каждой из вершин.
- Запросы: По свойству heavy-light декомпозиции, на пути от вершины к корню мы сменим не более путей. Значит время выполнения запроса также .
Реализация
Ниже будет приведена реализация запроса сумма на пути между любыми двумя вершинами в дереве без запросов модификации. Все запросы, сводящиеся к навешиванию дерева отрезков на пути из декомпозиции делаются похожим образом.
Опущены некоторые детали реализации: построение и дерево отрезков.
- — функция, позволяющая найти смещение вершины в пути относительно корня пути,
- — функция, позволяющая найти вес -ого ребра в -ом пути.
Пример реализации запроса суммы на пути:
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