Centroid decomposition

Centroid decomposition (рус. центроидная декомпозиция) — это структура данных, позволяющая отвечать на запросы на дереве. Чаще всего это запросы, связанные с нахождением функции на вершинах, связанных неравенством на расстояние между ними в дереве. Также иногда применяется для запросов на путях в дереве.

Введение

Рассмотрим [math]2[/math] задачи на обычном массиве (в дальнейшем мы будем их обобщать на случай дерева):

Задача [math]1[/math]

Задача:

Есть массив [math]a[/math] положительных целых чисел из [math]n[/math] элементов. Также дано число [math]W \geqslant 0[/math] и число [math]l[/math]. Требуется найти количество пар [math](i, j)[/math] индексов массива, таких что [math]|j - i| \leqslant l [/math] и [math]\sum\limits_{k=i}^{j} a_k \leqslant W[/math].

Задача [math]2[/math]:

Задача:

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

Для начала решим обе задачи. Первая задача решается методом «разделяй и властвуй» — давайте разделим массив [math]a[0 \dots n-1][/math] на 2 массива [math]a[0\dots\dfrac{n}{2} - 1][/math] и [math]a[\dfrac{n}{2} \dots n-1][/math] и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар [math](i, j)[/math], таких что [math]i \lt \dfrac{n}{2}, j \geqslant \dfrac{n}{2}[/math]. Для этого воспользуемся другой известной техникой — методом двух указателей. Посчитаем массив префиксных сумм для правой половины [math]pref[i] = \sum\limits_{j=\frac{n}{2}}^{i} a_j[/math] и суффиксных ([math]suf[i] = \sum\limits_{j=i}^{\frac{n}{2} + 1} a_j[/math]) — для левой. Заведем два указателя ([math]p_1[/math] и [math]p_2[/math]). Изначально установим [math]p_1 = \dfrac{n}{2} - l + 1, p_2 = \dfrac{n}{2}[/math]. Пока [math]p_2 - 1\gt \dfrac{n}{2}[/math] и

[math]pref[p_2] + suf[p_1] \gt W [/math] будем уменьшать [math]p_2[/math] на [math]1[/math]. Если после этого [math]pref[p_2] + suf[p_1] \leqslant W[/math], то к ответу прибавим [math](p_2 - \dfrac{n}{2} + 1) * (\dfrac{n}{2} - p_1)[/math], после чего увеличим [math]p_1[/math] на [math]1[/math]. Так будем делать, пока [math]p_1 \lt \dfrac{n}{2}[/math]. В конце сложим текущий ответ и ответы для половин массива — получим ответ на задачу. Асимптотика такого алгоритма: [math]T(n) = 2 * T(n / 2) + O(n) = O(n)[/math]

Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию «разделяй и властвуй» — дерево отрезков. Построим дерево отрезков, поддерживающее 2 вида запросов: присвоение в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив [math]b[/math], такой что [math]b_i = 0[/math], если в i-м городе принимает госпиталь и [math]b_i = 1[/math] иначе. Когда в каком-то городе открывается/закрывается госпиталь — делаем запрос на изменение в дереве отрезков. Когда требуется узнать ближайщий госпиталь к [math]i[/math]-му городу, можно воспользоваться одной из следующих идей:

• ([math]O(n \cdot log^2(n)[/math]) Бинарным поиском ищем ближайший слева и ближайший справа к i-му городу госпиталь (такой город [math]j[/math], что [math]\min\limits_{k=i..j}b_k= 1[/math]). Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков.
• ([math]O(n \cdot log(n)[/math]) Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновоременно и бинарный поиск, и спуск/подъем по дереву.

Статическая центроидная декомпозиция

Перейдем к обобщению поставленных задач на случай дерева. Начнем, как и полагается, с первой:

Задача:

Есть взвешенное дерево [math]t[/math] из [math]n[/math] вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа [math]W \geqslant 0[/math] и [math]l[/math]. Требуется найти количество пар [math](i, j)[/math] вершин дерева, таких что расстояние между ними не превосходит [math]l[/math] по числу ребер и не превосходит [math]W[/math] по сумме весов.

Для решения новой задачи применим ту же идею, что и была до этого — разделяй и властвуй. Для этого нам потребуется следующий объект:

Определение:

Центроидом дерева (англ. centroid) называется такая вершина [math]v[/math] дерева [math]t[/math], после удаления которой дерево разбивается на несколько ([math]k[/math]) поддеревьев [math]t_1, t_2,\dots, t_k[/math], таких что для каждого [math]i[/math]: [math]|t_i| \leqslant \dfrac{n}{2}[/math], т.е. размер каждого поддерева не превосходит половины размера исходного дерева.

Итак, в случае дерева идея разделяй-и-властвуй из предыдущего пункта будет формулироваться так: найдем центроид. Предположим, что мы сумели найти центроид за [math]O(n)[/math], где [math]n[/math] — размер дерева. Тогда, как и в упрощенной версии задачи — рекурсивно найдем ответ для всех поддеревьев [math]t_1, t_2,\dots, t_k[/math], после чего попытаемся найти недостающие пары вершин, находящиехя в разных поддеревьях и удовлетворяющих вопросу задачи. Для этого будем отвечать на следующие запросы: пусть мы сейчас считаем все пары, где первая из вершин находится в поддереве [math]t_i[/math] и мы в некоторой структуре данных [math]S[/math] храним все вершины остальных деревьев (каждую вершину задаем парой [math](depth(v), length(v))[/math] — глубина вершины и длина пути до нее из корня поддерева), расстояние до которых от корня их поддерева не превышает [math]min(l, n)[/math]. Тогда просто пройдемся по всем вершинам [math]u[/math] поддерева [math]t_i[/math] и прибавим к ответу число вершин в структуре [math]S[/math], таких, что [math]depth(u) \leqslant l - depth(v)[/math] и [math]length(u) \leqslant l - length(v)[/math]. Это двумерные запросы, на которые можно отвечать за [math]O(log^2(n)[/math] с помощью 2d-дерева отрезков, либо за [math]O(log(n))[/math] с помощью техники поиска точек в d-мерном пространстве. Также читателю предлагается придумать и более эффективные и простые способы решить эту подзадачу.

Оценим итоговую асимптотику: [math]T(n) = k * T(n / k) + O(n \cdot log(n))[/math]. Решая это рекурентное соотношение, получим [math]O(n \cdot log(n))[/math].

Теперь докажем лемму о существовании центроида и опишем алгоритм его эффективного поиска.

Лемма о существовании центроида и алгоритм его нахождения.

Лемма:

В любом дереве [math]t[/math] существует центроид.

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

[math]\triangleright[/math]

Рассмотрим корень дерева [math](r)[/math]. Положим изначально [math]v = r[/math]. Изначально [math]|subtree(v)| = n[/math]. Среди всех детей [math]v[/math] выберем вершину [math]u[/math] с максимальным размером поддерева. Если [math]v[/math] — не центроид, то положим [math]v = u[/math] и продолжим выбор нового u, иначе — остановимся. Докажем, что мы в какой-то момент остановимся. Пусть в призвольный момент времени [math]v[/math] — не центроид и размер её наддерева меньше [math]\dfrac{n}{2}[/math], значит максимальное поддерево имеет размер больше чем [math]\dfrac{n}{2}[/math], т.е. [math]|subtree(u)| \gt \dfrac{n}{2}[/math], а значит размер "наддерева" вершины [math]u[/math] равен [math]n - |subtree(u)| \lt \dfrac{n}{2}[/math]. При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины [math]u[/math] не превосходит [math]|subtree(u)| - 1[/math], т.к. наддерево имеет размер меньше, чем поддерево [math]u[/math], а любое поддерево вершины [math]u[/math] имеет хотя бы на [math]1[/math] вершину меньше (сама вершина [math]u[/math]). По индукции получаем, что в любой момент времени размер наддерева вершины v меньше [math]\dfrac{n}{2}[/math], значит мы будем спускаться только вниз по дереву [math]t[/math], и при переходе к вершине [math]u[/math] — сыну [math]v[/math] размер максимального поддерева уменьшится как минимум на [math]1[/math]. Значит не более чем за [math]n[/math] шагов наши действия прекратятся и мы окажемся в центроиде дерева [math]t[/math], ч.т.д. Итак, мы конструктивно доказали существование центроида и привели линейный относительно размера дерева алгоритм его нахождения.

[math]\triangleleft[/math]

Реализация

Поиск центроида в дереве:

 int [math]\mathtt{findCentroid}[/math](int[] children[n], int v, int[] sz)
    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 [math]\mathtt{findCentroid}[/math](children, max_subtree, sz)

Шаблон решения произвольной задачи на статическую центроидную декомпозицию:

 [math]\mathtt{solve}[/math](int[] children[n], int v, int[] sz)
    c = [math]\mathtt{findCentroid}[/math](children, max_subtree, sz) // находим c — центроид поддерева вершины v 
    ch = children[c]
    [math]\mathtt{deleteEdges}[/math](c, children) // удаляем все ребра между вершиной с и детьми, чтобы мы не смогли из детей попасть в с. 
        Это полезно делать, если решение подзадачи для поддерева предполагает проход dfs 
    for c2 : ch[c]
         [math]\mathtt{solve}[/math](children, c2, sz)
    [math]\mathtt{mergeSolution}[/math](children, c2) // решаем для текущего поддерева 

Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)

Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией «разделяй и властвуй» — деревом отрезков. В предыдущем пункте мы определили статический аналог «разделяй и властвуй» для дерева. Теперь обобщим этот метод для динамических задач.

Определение:

Деревом центроидов (или центроидной декомпозицией) дерева [math]t[/math] называют дерево [math]T(t)[/math], построенное на вершинах дерева [math]t[/math] следующим образом: Пусть вершина [math]c[/math] — центроид дерева [math]t[/math]. Объявим его корнем нового дерева [math]T[/math]. Пусть при удалении вершины [math]c[/math] из дерева [math]t[/math] оно распалось на поддеревья [math]t_1, t_2,\dots, t_k[/math], тогда детьми вершины c объявим [math]T(t_1), T(t_t),\dots, T(t_k)[/math].

Свойства центроидной декомпозиции

Лемма:

Свойства центроидной декомпозиции: Глубина дерева центроидов не превосходит [math]log(n)[/math]. Каждая вершина [math]v[/math] дерева [math]t[/math] является центроидом одного из поддеревьев дерева [math]t[/math] Каждая вершина дерева [math]t[/math] принадлежит [math]O(log(n))[/math] поддеревьям дерева [math]T[/math] (еще говорят, что вершина принадлежит [math]O(log(n))[/math] центроидам дерева [math]t[/math], или что эти центроиды содержат вершину) Для любых вершин [math]u, v \in T (u \neq v)[/math] верно ровно одно из следующих трех утверждений: [math]T(v) \subset T(u)[/math] [math]T(u) \subset T(v)[/math] [math]T(u) \cap T(v) = \emptyset [/math] Простой путь между любой парой вершин [math]u, v[/math] в дереве [math]t[/math] содержит центроид [math]c \in T(t)[/math], такой что [math]u, v \in T(c)[/math].

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

[math]\triangleright[/math]

Действительно, т.к. размер поддерева [math]s[/math] каждой вершины [math]c[/math] дереве [math]T[/math] не превосходит [math]\dfrac{|subtree(c)|}{2}[/math], то при спуске в каждую следующую вершину на пути к любому листу в дереве [math]T[/math] размер поддерева вершины, в которой мы сейчас находимся, уменьшается как минимум на [math]2[/math]. Значит длина всего пути до листа не превосходит [math]log(n)[/math], ч.т.д. Второе свойство очевидно из построения дерева [math]T[/math], т.к. если вершина принадлежит дереву центроидов [math]T[/math], то она является центроидом, а из построения [math]T[/math] мы знаем, что каждая вершина исходного дерева принадлежит и дереву [math]T[/math]. Третье свойство — прямое следствие первых двух, т.к. вершина принадлежит любому центроиду [math]c[/math] т.и т.т., когда c — отец вершины [math]v[/math] в дереве центроидов. Т.к. вершина [math]v[/math] точно принадлежит дереву [math]T[/math] (свойство 2), то она лежит на каком-то пути в дереве [math]T[/math], причем все ее родители (центроиды) ее содержат. А по свойству 1 длина любого вертикального (и даже простого) пути есть [math]O(log(n))[/math], ч.т.д. Четвертое свойство очевидно из того, что [math]T[/math] — дерево. Т.к. [math]T(u)[/math] и [math]T(v)[/math] — поддеревья различных вершин дерева [math]T[/math], то либо они не пересекаются, либо [math]u[/math] — предок [math]v[/math], и значит [math]T(v) \subset T(u)[/math], либо [math]v[/math] — предок [math]u[/math], и значит [math]T(u) \subset T(v)[/math]. Для доказательства последнего свойства выберем в качестве вершины [math]c[/math] [math]lca(u, v)[/math] в дереве центроидов [math]T[/math]. Покажем, что так выбранная вершина [math]c[/math] удовлетворяет заявленным свойствам. То, что [math]u, v \in T(c)[/math] — очевидно по определению [math]lca[/math], т.к. каждый предок любой вершины в дереве центроидов содержит эту вершину. Теперь докажем, что [math]c[/math] лежит на пути между парой вершин [math]u, v[/math]. Т.к. [math]c = lca(u, v)[/math] в [math]T[/math], то из [math]c[/math] нет ребра в такого сына, который содержит одновременно [math]u[/math] и [math]v[/math] в своем поддереве (в дереве [math]T[/math]), значит после удаления [math]c[/math] дерево [math]t[/math] разделится на несколько поддеревьев, таких что вершины [math]u[/math] и [math]v[/math] окажутся в разных компонентах связности. А значит найдется такое ребро [math](c, x)[/math], которое принадлежало пути из [math]u[/math] в [math]v[/math], но после удаления [math]c[/math] удалилось. Это доказывает то, что вершина [math]c[/math] лежала на пути из [math]u[/math] в [math]v[/math], ч.т.д.

[math]\triangleleft[/math]

С помощью описанных свойств дерева [math]T[/math] мы можем решить задачу 2 для дерева:

Пример решения задачи с помощью центроидной декомпозиции

Задача:

Есть дерево [math]t[/math] из [math]n[/math] вершин. В каждый момент времени любая вершина дерева может быть либо помечена, либо нет. Изначально помечена только вершина номер [math]0[/math]. Дан список из [math]m[/math] запросов: Вершину [math]v[/math] пометили. С вершины [math]v[/math] сняли пометку. Найти номер ближайшей к [math]v[/math] помеченной вершины.

Решение:

Построим центроидную декомпозицию [math]T[/math] дерева [math]t[/math]. Изначально посчитаем для каждого центроида, содержащего вершину [math]0[/math] посчитаем расстояние до вершины [math]0[/math]. Для этого воспользуемся методом двоичных подъемов для поиска lca пары вершин в дереве, а также тем фактом, что если глубина [math]h(v)[/math] вершины [math]v[/math] в дереве определена как расстояние от корня до вершины [math]v[/math], то длина пути между парой вершин [math](u, v)[/math] есть [math]len(u, v) = h(u) + h(v) - 2 \cdot h(lca(u, v))[/math]. Если изначально предпосчитать проходом dfs величины [math]h(v)[/math] за [math]O(n)[/math], то ответ на запрос [math]len(u, v)[/math] можно делать за время [math]O(log(n))[/math] с [math]O(n \cdot log(n))[/math]доп. памятью. Также можно воспользоваться техникой сведения задачи LCA к RMQ и решить с [math]O(n)[/math] дополнительной памятью и [math]O(1)[/math] времени на запрос. Теперь научимся отвечать на запросы. Из последнего свойства центроидной декомпозиции видно, что если [math]u[/math] — искомая ближайшая помеченная вершина к [math]v[/math], то путь между ними содержит центроид [math]c[/math], такой что [math]u, v \in T(c)[/math], причем [math]c[/math] — предок одновременно вершин [math]u, v[/math] в дереве[math]T[/math]. Поэтому заведем двоичное дерево поиска для каждого центроида [math]c \in T[/math]. В этой структуре для каждой вершины [math]c[/math] будем хранить пары [math](len(c, u), u)[/math] для всех помеченных вершин [math]u[/math] в поддереве центроидов [math]T(c)[/math]. Когда приходит запрос пометить вершину [math]v[/math] — добавим в структуру данных для всех предков [math]p_c[/math] вершины [math]v[/math] в дереве [math]T[/math] пары [math](len(p_c, v), v)[/math]. Мы совершим [math]O(log(n))[/math] добавлений, затратив [math]O(log(n))[/math] действий на каждое. Запрос снятия пометки с вершины обрабатывается аналогичными удалениями. Запрос поиска ближайшей к [math]v[/math] помеченной вершины — это запрос поиска вершины u, такой что величина [math]len(c, u) + len(c, v)[/math] минимальна, где [math]c[/math] — предок [math]v[/math] в дереве центроидов (по пятому свойству, нас интересуют именно такие [math]c[/math]). Этот запрос занимает так же [math]O(log^2(n))[/math] времени.

Итак, мы научились решать задачу с [math]O(n)[/math] дополнительной памятью и временной сложностью [math]O(log^2(n))[/math] на запрос любого типа с предварительным предпосчетом за [math]O(n)[/math].

Варианты хранения центроидной декомпозиции

Для хранения дерева центроидов [math]T[/math] есть [math]2[/math] подхода, имеющих свои преимущества и недостатки:

• Для каждой вершины [math]v[/math] исходного дерева запомним величину [math]p_v[/math] — номер предка вершины [math]v[/math] в дереве [math]T[/math].

Этот подход наиболее экономный по памяти ([math]O(n)[/math]), но уступает в скорости и функциональности.

• Для каждой вершины [math]v[/math] исходного дерева будем хранить весь массив предков [math]p[v][/math] в дереве центроидов.

Этот подход уступает в количестве необходимой дополнительной памяти ([math]O(n \cdot log(n))[/math] суммарно), но имеет ряд преимуществ:

1. При проходе по массиву предков фиксированной вершины будет выигрыш в скорости работы, т.к. весь массив будет лежать непрерывным блоком данных и следовательно будет закэширован
2. На массиве предков можно строить различные структуры данных (такие как, например, дерево отрезков) для быстрого (в случае с деревом отрезков [math]O(log(log(n)))[/math] на запрос) поиска предка с необходимыми свойствами. Так, например, в описанной выше задаче про помеченные вершины наибольшего общего предка можно искать методом двоичных подъемов за [math]O(log(log(n))[/math] на запрос, т.к. размер массива предков есть [math]O(log(n))[/math] (по свойству 1 центроидной декомпозиции). Используя эту оптимизацию можно получить время [math]O(log(n)) + O(log(log(n)) = O(log(n))[/math] на запрос нахождения ближайшей помеченной вершины. Чтобы добиться улучшенной асимптотики для запросов изменения можно хранить дерево отрезков на каждом из путей [math]p[v][/math], в каждой вершине которого хранить двоичное дерево поиска и поддерживать отложенные операции. Тогда ответ на эти запросы будет занимать [math]O(log(n) \cdot log(log(n))[/math] времени.

См. также

• Дерево отрезков
• Heavy-light декомпозиция
• Метод двоичного подъема