Изменения

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

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

Задача <math>1</math>:

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

Задача <math>2</math>:

|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида :* дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что который может принимать больных и <tex>abs{|u - v}|</tex> минимально возможное.

Первая задача решается методом [[Сортировка_слиянием|qevide&conqure (рус. разделяй «разделяй и властвуй)властвуй»]] {{- --}} давайте разделим массив <tex>a[0...\dots n-1]</tex> на 2 массива <tex>a[0...\fracdots\dfrac{n}{2} - 1]</tex> и <tex>a[\fracdfrac{n}{2}...\dots n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \fracdfrac{n}{2}, \text{ }j \geqslant \fracdfrac{n}{2}</tex>. Для этого воспользуемся другой известной техникой {{--- }} методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_sum\limits_{j=\frac{n/}{2}}^{i} a_j</tex> и суффиксных (<tex>(suf[i] = \sum_sum\limits_{j=i}^{\frac{n/}{2 } + 1} a_j)</tex>) {{--- }} для левой. Заведем два указателя (<tex>p1(p_1</tex> и <tex>p2p_2)</tex>). Изначально установим <tex>p1 p_1 = \fracdfrac{n}{2} - l + 1, p2 \text{ }p_2 = \fracdfrac{n}{2}</tex>. Пока <tex>p2 p_2 - 1> \fracdfrac{n}{2}</tex> и

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

Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию qevide&conqure «разделяй и властвуй» {{--- }} [[Дерево_отрезков._Построение|дерево отрезков]]. Построим дерево отрезков,поддерживающее 2 вида запросов : присвоение в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив <math>b[]</math>, такой что <tex>b[i] b_i = 0</tex>, если в <math>i</math>-м городе принимает госпиталь и <tex>b[i] b_i = 1</tex> иначе. Когда в каком-то городе открывается/закрывается госпиталь {{- --}} делаем запрос на изменение в дереве отрезков. Когда требуется узнать ближайщий ближайший госпиталь к <math>i</math>-му городу, можно воспользоваться одной из следующих идей : а) (* <tex>(O(n \cdot log^2(n))</tex>) Бинарным поиском ищем ближайший слева и ближайший справа к <math>i</math>-му городу госпиталь (такой город <math>j</math>, что <mathtex>\min(\limits_{k=i...j) }b_k= 1)</mathtex>). Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков. б) (* <tex>(O(n \cdot \log(n))</tex>) Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновоременно одновременно и бинарный поиск, и спуск/подъем по дереву.

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

|definition = Есть взвешенное дерево <tex>t</tex> из <tex>n</tex> вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа <tex>W >= \geqslant 0</tex> и <tex>l</tex>. Требуется найти количество пар <tex>(i, j)</tex> вершин дерева, таких что расстояние между ними не превосходит <math>l</math> по числу ребер и не превосходит <math>W</math> по сумме весов<ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160324a1.pdf Сайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>.

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

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

Итак, в случае дерева идея разделяй-«разделяй и-властвуй властвуй» из предыдущего пункта будет формулироваться так : [[#l1|найдем центроид (доказательство её существования и алгоритм нахождение см. далее)]]. Предположим, что мы сумели найти центроид за <math>O(n)</math>, где <math>n</math> {{-- -}} размер дерева. Тогда, как и в упрощенной версии задачи {{--- }} рекурсивно найдем ответ для всех поддеревьев <tex>t_1, t_2,...\dots, t_k</tex>, после чего попытаемся найти недостающие пары вершин, находящиехя находящиеся в разных поддеревьях и удовлетворяющих вопросу задачи. Для этого будем отвечать на следующие запросы : пусть мы сейчас считаем все пары, где первая из вершин находится в поддереве <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>, таких, что <tex>depth(u) \leqslant l - depth(v)</tex> и <tex>length(u) \leqslant l - length(v)</tex>. Это двумерные запросы, на которые можно отвечать за <math>O(log^2(n)</math> с помощью [[Многомерное_дерево_отрезков|2d-дерева отрезков]], либо за <math>O(\log(n))</math> с помощью [[Перечисление_точек_в_произвольном_прямоугольнике_за_n_*_log_%5E(d_-_1)_n_(range_tree)|техники поиска точек в d-мерном пространстве]]. Также читателю предлагается придумать и более эффективные и простые способы решить эту подзадачу.

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

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

{{Лемма|id=l1

В любом дереве <math>t </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> и продолжим выбор нового <math>u</math>, иначе {{--- }} остановимся. Докажем, что мы в какой-то момент остановимся. Пусть в призвольный произвольный момент времени <math>v</math> {{--- }} не центроид и размер её наддерева меньше <math>\fracdfrac{n}{2}</math>, значит максимальное поддерево имеет размер больше чем <math>\fracdfrac{n}{2}</math>, т.е. то есть <math>|subtree(u)| > \fracdfrac{n}{2}</math>, а значит размер "наддерева" вершины <math>u</math> равен <tex>n - |subtree(u)| < \fracdfrac{n}{2}</tex>. При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины <math>u</math> не превосходит <math>|subtree(u)| - 1</math>, т.к. так как наддерево имеет размер меньше, чем поддерево <math>u</math>, а любое поддерево вершины <math>u</math> имеет хотя бы на <math>1</math> вершину меньше (сама вершина <math>u)</math>). По индукции получаем, что в любой момент времени размер наддерева вершины <math>v </math> меньше <math>\fracdfrac{n}{2}</math>, значит мы будем спускаться только вниз по дереву <math>t</math>, и при переходе к вершине <math>u</math> {{--- }} сыну <math>v</math> размер максимального поддерева уменьшится как минимум на <math>1</math>. Значит не более чем за <math>n</math> шагов наши действия прекратятся и мы окажемся в центроиде дерева <math>t</math>, ч.т.д.

'''int''' <tex>\mathtt{findCentroid}</tex>('''int[]''' children[n], '''int''' v, '''int[]''' sz[n], '''int''' tree_size)

'''if''' sz[u] > sz[v] tree_size / 2 '''and ''' sz[u] > sz[max_subtree] <font color=green>// считаем sz[-1] = 0 </font >

'''return''' <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz, tree_size)

<tex>\mathtt{solve}</tex>('''int[]''' children[n], '''int''' v, '''int[]''' sz[n]) c = <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz, sz[v]) <font color=green>// находим c {{- --}} центроид поддерева вершины v </font >

<tex>\mathtt{deleteEdges}</tex>(c, children) <font color=green>// удаляем все ребра из вершины между вершиной с в детейи детьми, чтобы мы не смогли из детей попасть в с. Это полезно делать, если решение подзадачи для поддерева предполагает проход <math>dfs </math> </font >

<tex>\mathtt{solveForSubtreemergeSolution}</tex>(children, c2) <font color=green>// решаем для текущего поддерева </font >

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

|definition="'''Деревом центроидов ''' (или центроидной декомпозицией, англ. ''centroid decomposition tree'')" дерева <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> оно распалось на поддеревья <tex>t_1, t_2,...\dots, t_k</tex>, а центроиды этих поддеревьев - тогда детьми вершины c объявим <tex>c_1, c_2, ..., c_k</tex> исходного дерева, соответственно. Проведем ребра из вершины <math>c</math> в дереве <math>T</math> ребра во все вершины <tex>c_1, c_2,..., c_k</tex>.* Рекурсивно перейдем к построению для поддеревьев <tex>(t_1), T(t_2),...\dots, T(t_k)</tex>.

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

# Действительно, т.к. так как размер поддерева <math>s</math> каждой вершины <math>c</math> дереве <math>T</math> не превосходит <tex>\fracdfrac{|subtree(c)|}{2}</tex>, то при спуске в каждую следующую вершину на пути к любому листу в дереве <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> т.и т.т., когда <math>c </math> {{--- }} отец вершины <math>v</math> в дереве центроидов. Т.к. Так как вершина <math>v</math> точно принадлежит дереву <math>T</math> (свойство <math>2</math>), то она лежит на каком-то пути в дереве <math>T</math>, причем все ее родители (центроиды) ее содержат. А по свойству <math>1 </math> длина любого вертикального (и даже простого) пути есть <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>, и значит <tex>T(v) \subset T(u)</tex>, либо <math>v</math> {{---}} предок <math>u</math>, и значит <tex>T(u) \subset T(v)</tex>.# Для доказательства последнего свойства в качестве вершины <math>c</math> выберем <math>lca(u, v)</math> в дереве центроидов <math>T</math>. Покажем, что так выбранная вершина <math>c</math> удовлетворяет заявленным свойствам. То, что <tex>u, v \in T(c)</tex> {{---}} очевидно по определению <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>T</math> мы можем решить задачу <math>2 </math> для дерева :

|definition = Есть страна, дерево <math>nt</math> городов которой связаны двустронними дорогами, причем так, чтобы получился минимальный связный граф на из <math>n-1</math> ребрахвершин. В каждом городе есть госпиталь, который в каждый момент времени любая вершина дерева может быть либо открытпомечена, либо закрытнет. Изначально помечена только вершина номер <math>0</math>. Дан список из <math>m</math> событий запросов: * Госпиталь в городе Вершину <math>v</math> открылсяпометили.* Госпиталь в городе С вершины <math>v</math> закрылсясняли пометку.* Больной из города Найти номер ближайшей к <math>v</math> хочет узнать номер ближайшего города, госпиталь которого открытпомеченной вершины<ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160324a1.pdf Сайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>.

Построим центроидную декомпозицию <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> есть <tex>len(u, v) = h(u) + h(v) - 2 \cdot h(lca(u, v))</tex>. Если изначально предпосчитать проходом [[Обход_в_глубину,_цвета_вершин| <math>dfs</math>]] величины <math>h(v)</math> за <math>O(n)</math>, то ответ на запрос <math>len(u, v)</math> можно делать за время <math>O(\log(n))</math> с <tex>O(n \cdot \log(n)) </tex>доп. памятью. Также можно воспользоваться техникой [[Сведение_задачи_LCA_к_задаче_RMQ|сведения задачи LCA к RMQ]] и решить с <math>O(n)</math> дополнительной памятью и <math>O(1)</math> времени на запрос. Теперь научимся отвечать на запросы. Из последнего свойства центроидной декомпозиции видно, что если <math>u</math> {{---}} искомая ближайшая помеченная вершина к <math>v</math>, то путь между ними содержит центроид <math>c</math>, такой что <tex>u, v \in T(c)</tex>, причем <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> помеченной вершины {{---}} это запрос поиска вершины <math>u</math>, такой что величина <math>len(c, u) + len(c, v)</math> минимальна, где <math>c</math> {{---}} предок <math>v</math> в дереве центроидов (по пятому свойству, нас интересуют именно такие <math>c)</math>. Этот запрос занимает так же <tex>O(log^2(n))</tex> времени. Итак, мы научились решать задачу с <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> в дереве центроидов. Этот подход уступает в количестве необходимой дополнительной памяти <tex>(O(n \cdot \log(n))</tex> суммарно), но имеет ряд преимуществ: #При проходе по массиву предков фиксированной вершины будет выигрыш в скорости работы, так как весь массив будет лежать непрерывным блоком данных и следовательно будет закэширован# На массиве предков можно строить различные структуры данных (такие как, например, дерево отрезков) для быстрого (в случае с деревом отрезков <math>O(log(\log(n)))</math> на запрос) поиска предка с необходимыми свойствами. Так, например, в описанной выше задаче про помеченные вершины наибольшего общего предка можно искать методом двоичных подъемов за <math>O(\log(\log(n))</math> на запрос, так как размер массива предков есть <math>O(\log(n))</math> (по свойству <math>1</math> центроидной декомпозиции). Используя эту оптимизацию можно получить время <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> времени.

== Примечания ==