Centroid decomposition
Centroid decomposition (рус. центроидная декомпозиция) — это структура данных, позволяющая отвечать на запросы на дереве. Чаще всего это запросы, связанные с нахождением функции на вершинах, связанных неравенством на расстояние между ними в дереве. Также иногда применяется для запросов на путях в дереве.
Введение
Рассмотрим
задачи на обычном массиве (в дальнейшем мы будем их обобщать на случай дерева):Задача
Задача: |
Есть массив | положительных целых чисел из элементов. Также дано число и число . Требуется найти количество пар индексов массива, таких что и .
Задача
:Задача: |
Есть прямая дорога, на которой расположены
| городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида:
Для начала решим обе задачи. Первая задача решается методом «разделяй и властвуй» — давайте разделим массив на 2 массива и и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар , таких что . Для этого воспользуемся другой известной техникой — методом двух указателей. Посчитаем массив префиксных сумм для правой половины и суффиксных ( ) — для левой. Заведем два указателя ( и ). Изначально установим . Пока и
будем уменьшать на . Если после этого , то к ответу прибавим , посго, увеличим на <math/math>. Так будем делать, пока . В конце сложим текущий ответ и ответы для половин массива — получим ответ на задачу. Асимптотика такого алгоритма:
Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию «разделяй и властвуй» — дерево отрезков. Построим дерево отрезков, поддерживающее 2 вида запросов: присвоение в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив , такой что , если в i-м городе принимает госпиталь и иначе. Когда в каком-то городе открывается/закрывается госпиталь — делаем запрос на изменение в дереве отрезков. Когда требуется узнать ближайщий госпиталь к -му городу, можно воспользоваться одной из следующих идей: а) ( ) Бинарным поиском ищем ближайший слева и ближайший справа к i-му городу госпиталь (такой город , что ). Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков. б) ( ) Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновоременно и бинарный поиск, и спуск/подъем по дереву.
Статическая центроидная декомпозиция
Перейдем к обобщению поставленных задач на случай дерева. Начнем, как и полагается, с первой:
Задача: |
Есть взвешенное дерево | из вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа и . Требуется найти количество пар вершин дерева, таких что расстояние между ними не превосходит по числу ребер и не превосходит по сумме весов.
(Задача D со сборов СПБ к РОИ-2016[1])
Для решения новой задачи применим ту же идею, что и была до этого — разделяй и властвуй. Для этого нам потребуется следующий объект:
Определение: |
Центроидом дерева (англ. centroid) называется такая вершина | дерева , после удаления которой дерево разбивается на несколько ( ) поддеревьев , таких что для каждого : , т.е. размер каждого поддерева не превосходит половины размера исходного дерева.
Итак, в случае дерева идея разделяй-и-властвуй из предыдущего пункта будет формулироваться так: найдем центроид. Предположим, что мы сумели найти центроид за 2d-дерева отрезков, либо за с помощью техники поиска точек в d-мерном пространстве. Также читателю предлагается придумать и более эффективные и простые способы решить эту подзадачу.
, где — размер дерева. Тогда, как и в упрощенной версии задачи — рекурсивно найдем ответ для всех поддеревьев , после чего попытаемся найти недостающие пары вершин, находящиехя в разных поддеревьях и удовлетворяющих вопросу задачи. Для этого будем отвечать на следующие запросы: пусть мы сейчас считаем все пары, где первая из вершин находится в поддереве и мы в некоторой структуре данных храним все вершины остальных деревьев (каждую вершину задаем парой — глубина вершины и длина пути до нее из корня поддерева), расстояние до которых от корня их поддерева не превышает . Тогда просто пройдемся по всем вершинам поддерева и прибавим к ответу число вершин в структуре , таких, что и . Это двумерные запросы, на которые можно отвечать за с помощьюОценим итоговую асимптотику:
. Решая это рекурентное соотношение, получим .Теперь докажем лемму о существовании центроида и опишем алгоритм его эффективного поиска.
Лемма о существовании центроида и алгоритм его нахождения.
Лемма: |
В любом дереве существует центроид. |
Доказательство: |
Рассмотрим корень дерева Итак, мы конструктивно доказали существование центроида и привели линейный относительно размера дерева алгоритм его нахождения. . Положим изначально . Изначально . Среди всех детей выберем вершину с максимальным размером поддерева. Если — не центроид, то положим и продолжим выбор нового u, иначе — остановимся. Докажем, что мы в какой-то момент остановимся. Пусть в призвольный момент времени — не центроид и размер её наддерева меньше , значит максимальное поддерево имеет размер больше чем , т.е. , а значит размер "наддерева" вершины равен . При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины не превосходит , т.к. наддерево имеет размер меньше, чем поддерево , а любое поддерево вершины имеет хотя бы на вершину меньше (сама вершина ). По индукции получаем, что в любой момент времени размер наддерева вершины v меньше , значит мы будем спускаться только вниз по дереву , и при переходе к вершине — сыну размер максимального поддерева уменьшится как минимум на . Значит не более чем за шагов наши действия прекратятся и мы окажемся в центроиде дерева , ч.т.д. |
Реализация
Поиск центроида в дереве:
int(int[] children[n], int v, int sz[n]) max_subtree = -1 for u : children(v) if sz[u] > sz[v] / 2 and sz[u] > sz[max_subtree] // считаем sz[-1] = 0 max_subtree = u if max_subtree == -1 return v else return (children, max_subtree, sz)
Шаблон решения произвольной задачи на статическую центроидную декомпозицию:
(int[] children[n], int v, int sz[n]) c = (children, max_subtree, sz) // находим c — центроид поддерева вершины v ch = children[c] (c, children) // удаляем все ребра между вершиной с и детьми, чтобы мы не смогли из детей попасть в с. Это полезно делать, если решение подзадачи для поддерева предполагает проход dfs for c2 : ch[c] (children, c2, sz) (children, c2) // решаем для текущего поддерева
Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией «разделяй и властвуй» — деревом отрезков. В предыдущем пункте мы определили статический аналог «разделяй и властвуй» для дерева. Теперь обобщим этот метод для динамических задач.
Определение: |
Деревом центроидов (или центроидной декомпозицией) дерева
| называют дерево , построенное на вершинах дерева следующим образом:
Свойства центроидной декомпозиции
Лемма: |
Свойства центроидной декомпозиции:
|
Доказательство: |
|
С помощью описанных свойств дерева
мы можем решить задачу 2 для дерева:Пример решения задачи с помощью центроидной декомпозиции
Задача: |
Есть дерево
| из вершин. В каждый момент времени любая вершина дерева может быть либо помечена, либо нет. Изначально помечена только вершина номер . Дан список из запросов:
(Задача C со сборов СПБ к РОИ-2016[2])
Решение:
Построим центроидную декомпозицию методом двоичных подъемов для поиска lca пары вершин в дереве, а также тем фактом, что если глубина вершины в дереве определена как расстояние от корня до вершины , то длина пути между парой вершин есть . Если изначально предпосчитать проходом dfs величины за , то ответ на запрос можно делать за время с доп. памятью. Также можно воспользоваться техникой сведения задачи LCA к RMQ и решить с дополнительной памятью и времени на запрос. Теперь научимся отвечать на запросы. Из последнего свойства центроидной декомпозиции видно, что если — искомая ближайшая помеченная вершина к , то путь между ними содержит центроид , такой что , причем — предок одновременно вершин в дереве . Поэтому заведем двоичное дерево поиска для каждого центроида . В этой структуре для каждой вершины будем хранить пары для всех помеченных вершин в поддереве центроидов . Когда приходит запрос пометить вершину — добавим в структуру данных для всех предков вершины в дереве пары . Мы совершим добавлений, затратив действий на каждое. Запрос снятия пометки с вершины обрабатывается аналогичными удалениями. Запрос поиска ближайшей к помеченной вершины — это запрос поиска вершины u, такой что величина минимальна, где — предок в дереве центроидов (по пятому свойству, нас интересуют именно такие ). Этот запрос занимает так же времени.
дерева . Изначально посчитаем для каждого центроида, содержащего вершину посчитаем расстояние до вершины . Для этого воспользуемсяИтак, мы научились решать задачу с
дополнительной памятью и временной сложностью на запрос любого типа с предварительным предпосчетом за .Варианты хранения центроидной декомпозиции
Для хранения дерева центроидов
есть подхода, имеющих свои преимущества и недостатки:- Для каждой вершины исходного дерева запомним величину — номер предка вершины в дереве .
Этот подход наиболее экономный по памяти (
), но уступает в скорости и функциональности.- Для каждой вершины исходного дерева будем хранить весь массив предков в дереве центроидов.
Этот подход уступает в количестве необходимой дополнительной памяти (
суммарно), но имеет ряд преимуществ:- При проходе по массиву предков фиксированной вершины будет выигрыш в скорости работы, т.к. весь массив будет лежать непрерывным блоком данных и следовательно будет закэширован
- На массиве предков можно строить различные структуры данных (такие как, например, дерево отрезков) для быстрого (в случае с деревом отрезков на запрос) поиска предка с необходимыми свойствами. Так, например, в описанной выше задаче про помеченные вершины наибольшего общего предка можно искать методом двоичных подъемов за на запрос, т.к. размер массива предков есть (по свойству 1 центроидной декомпозиции). Используя эту оптимизацию можно получить время на запрос нахождения ближайшей помеченной вершины. Чтобы добиться улучшенной асимптотики для запросов изменения можно хранить дерево отрезков на каждом из путей , в каждой вершине которого хранить двоичное дерево поиска и поддерживать отложенные операции. Тогда ответ на эти запросы будет занимать времени.