Викиконспекты - Вклад участника [ru]

Centroid decomposition

2017-06-14T10:53:47Z

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

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

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

Задача 1
{{Задача
|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_{i=0}^{n - 1} a_i \leqslant W</tex>.
}}
Задача 2:
{{Задача
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида :
* дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что <tex>|u - v|</tex> минимально возможное.
* дан город <tex>v</tex> и сказано, что больше он не будет принимать больных
* дан город <tex>v</tex> и сказано, что теперь он может принимать больных
}}
Для начала решим обе задачи.
Первая задача решается методом [[Сортировка_слиянием|qevide&conqure (рус. разделяй и властвуй)]] - давайте разделим массив <tex>a[0...n-1]</tex> на 2 массива <tex>a[0...\frac{n}{2} - 1]</tex> и <tex>a[\frac{n}{2}...n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \frac{n}{2}, j \geqslant \frac{n}{2}</tex>. Для этого воспользуемся другой известной техникой - методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_{j=\frac{n}{2}}^{i} a_j</tex> и суффиксных (<tex>suf[i] = \sum_{j=i}^{\frac{n}{2} + 1} a_j</tex>) - для левой. Заведем два указателя (<tex>p_1</tex> и <tex>p_2</tex>). Изначально установим <tex>p_1 = \frac{n}{2} - l + 1, p_2 = \frac{n}{2}</tex>. Пока <tex>p_2 - 1> \frac{n}{2}</tex> и

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

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

== Статическая центроидная декомпозиция ==
Перейдем к обобщению поставленных задач на случай дерева. Начнем, как и полагается, с первой:
{{Задача
|definition = Есть взвешенное дерево <tex>t</tex> из <tex>n</tex> вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа <tex>W >= 0</tex> и <tex>l</tex>. Требуется найти количество пар <tex>(i, j)</tex> вершин дерева, таких что расстояние между ними не превосходит <math>l</math> по числу ребер и не превосходит <math>W</math> по сумме весов.
}}

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

{{Определение
|id=191213
|definition =
'''Центроидом дерева''' (англ. ''centroid'') называется такая вершина <math>v</math> дерева <math>t</math>, после удаления которой дерево разбивается на несколько (<math>k</math>) поддеревьев <tex>t_1, t_2,..., t_k</tex>, таких что для каждого <math>i</math> : <tex>|t_i| \leqslant \frac{n}{2}</tex>, т.е. размер каждого поддерева не превосходит половины размера исходного дерева.
}}
Итак, в случае дерева идея разделяй-и-властвуй из предыдущего пункта будет формулироваться так : найдем центроид (доказательство её существования и алгоритм нахождение см. далее). Предположим, что мы сумели найти центроид за <math>O(n)</math>, где <math>n</math> - размер дерева. Тогда, как и в упрощенной версии задачи - рекурсивно найдем ответ для всех поддеревьев <tex>t_1, t_2,..., 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 * T(n / k) + O(n \cdot log(n))</tex>. Решая это рекурентное соотношение, получим <math>O(n \cdot log(n))</math>.

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

=== Лемма о существовании центроида и алгоритм его нахождения. ===
{{Лемма
|statement=
В любом дереве t существует центроид.
|proof=
Рассмотрим корень дерева <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>\frac{n}{2}</math>, значит максимальное поддерево имеет размер больше чем <math>\frac{n}{2}</math>, т.е. <math>|subtree(u)| > \frac{n}{2}</math>, а значит размер "наддерева" вершины <math>u</math> равен <tex>n - |subtree(u)| < \frac{n}{2}</tex>. При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины <math>u</math> не превосходит <math>|subtree(u)| - 1</math>, т.к. наддерево имеет размер меньше, чем поддерево <math>u</math>, а любое поддерево вершины <math>u</math> имеет хотя бы на <math>1</math> вершину меньше (сама вершина <math>u</math>). По индукции получаем, что в любой момент времени размер наддерева вершины v меньше <math>\frac{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])
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''' <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz)

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

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

== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией devide&conqure - деревом отрезков. В предыдущем пункте мы определили статический оналог devide&conqure для дерева. Теперь обобщим этот метод для динамических задач.
{{Определение
|definition=
'''Деревом центроидов (или центроидной декомпозицией)''' дерева <math>t</math> называют дерево <math>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,..., t_k</tex>, а центроиды этих поддеревьев - вершины <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_2,..., t_k</tex>.
}}

{{Лемма
|statement=
Свойства центроидной декомпозиции :
* Глубина дерева центроидов не превосходит <tex>log(n)</tex>.
* Каждая вершина <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>)
|proof=
Действительно, т.к. размер поддерева <math>s</math> каждой вершины <math>c</math> дереве <math>T</math> не превосходит <tex>\frac{|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> т.и т.т., когда c - отец вершины <math>v</math> в дереве центроидов. Т.к. вершина <math>v</math> точно принадлежит дереву <math>T</math> (свойство 2), то она лежит на каком-то пути в дереве <math>T</math>, причем все ее родители (центроиды) ее содержат. А по свойству 1 длина любого вертикального (и даже простого) пути есть <math>O(log(n))</math>, ч.т.д.
}}

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

{{Задача
|definition = Есть страна, <math>n</math> городов которой связаны двустронними дорогами, причем так, чтобы получился минимальный связный граф на <math>n-1</math> ребрах. В каждом городе есть госпиталь, который в каждый момент времени может быть либо открыт, либо закрыт. Дан список из <math>m</math> событий :
* Госпиталь в городе <math>v</math> открылся.
* Госпиталь в городе <math>v</math> закрылся.
* Больной из города <math>v</math> хочет узнать номер ближайшего города, госпиталь которого открыт.
}}

Решение :

Построим центроидную декомпозицию <math>T</math> дерева городов <math>t</math>,

// TODO :: дописать решение (мой код : https://drivenotepad.github.io/app/?state={%22action%22:%22open%22,%22ids%22:[%220Bw29IKNdcznCYnVFbVo2alZiSzA%22]})

== Варианты реализации ==
// TODO :: написать про то, что можно хранить предков (+память О(n), - скорость, - ничего нельзя сделать), а можно для каждой вершины - массив содержащих ее центроидов (+скорость(кэш), +масштабируемость(структуры данных на путях), - память n*logn)

==См. также==

*[[:Дерево_отрезков._Построение|Дерево отрезков]]
*[[:Heavy-light_декомпозиция|Heavy-light декомпозиция]]
*[[:Метод_двоичного_подъема| Метод двоичного подъема]]

== Примечания ==
<references/>

[[Категория:Алгоритмы и структуры данных]]

Centroid decomposition

2017-06-14T10:52:20Z

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

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

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

Задача 1
{{Задача
|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_{i=0}^{n - 1} a_i \leqslant W</tex>.
}}
Задача 2:
{{Задача
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида :
* дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что <tex>|u - v|</tex> минимально возможное.
* дан город <tex>v</tex> и сказано, что больше он не будет принимать больных
* дан город <tex>v</tex> и сказано, что теперь он может принимать больных
}}
Для начала решим обе задачи.
Первая задача решается методом [[Сортировка_слиянием|qevide&conqure (рус. разделяй и властвуй)]] - давайте разделим массив <tex>a[0...n-1]</tex> на 2 массива <tex>a[0...\frac{n}{2} - 1]</tex> и <tex>a[\frac{n}{2}...n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \frac{n}{2}, j \geqslant \frac{n}{2}</tex>. Для этого воспользуемся другой известной техникой - методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_{j=\frac{n}{2}}^{i} a_j</tex> и суффиксных (<tex>suf[i] = \sum_{j=i}^{\frac{n}{2} + 1} a_j</tex>) - для левой. Заведем два указателя (<tex>p_1</tex> и <tex>p_2</tex>). Изначально установим <tex>p_1 = \frac{n}{2} - l + 1, p_2 = \frac{n}{2}</tex>. Пока <tex>p_2 - 1> \frac{n}{2}</tex> и

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

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

== Статическая центроидная декомпозиция ==
Перейдем к обобщению поставленных задач на случай дерева. Начнем, как и полагается, с первой:
{{Задача
|definition = Есть взвешенное дерево <tex>t</tex> из <tex>n</tex> вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа <tex>W >= 0</tex> и <tex>l</tex>. Требуется найти количество пар <tex>(i, j)</tex> вершин дерева, таких что расстояние между ними не превосходит <math>l</math> по числу ребер и не превосходит <math>W</math> по сумме весов.
}}

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

{{Определение
|id=191213
|definition =
'''Центроидом дерева''' (англ. ''centroid'') называется такая вершина <math>v</math> дерева <math>t</math>, после удаления которой дерево разбивается на несколько (<math>k</math>) поддеревьев <tex>t_1, t_2,..., t_k</tex>, таких что для каждого <math>i</math> : <tex>|t_i| \leqslant \frac{n}{2}</tex>, т.е. размер каждого поддерева не превосходит половины размера исходного дерева.
}}
Итак, в случае дерева идея разделяй-и-властвуй из предыдущего пункта будет формулироваться так : найдем центроид (доказательство её существования и алгоритм нахождение см. далее). Предположим, что мы сумели найти центроид за <math>O(n)</math>, где <math>n</math> - размер дерева. Тогда, как и в упрощенной версии задачи - рекурсивно найдем ответ для всех поддеревьев <tex>t_1, t_2,..., 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 * T(n / k) + O(n \cdot log(n))</tex>. Решая это рекурентное соотношение, получим <math>O(n \cdot log(n))</math>.

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

=== Лемма о существовании центроида и алгоритм его нахождения. ===
{{Лемма
|statement=
В любом дереве t существует центроид.
|proof=
Рассмотрим корень дерева <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>\frac{n}{2}</math>, значит максимальное поддерево имеет размер больше чем <math>\frac{n}{2}</math>, т.е. <math>|subtree(u)| > \frac{n}{2}</math>, а значит размер "наддерева" вершины <math>u</math> равен <tex>n - |subtree(u)| < \frac{n}{2}</tex>. При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины <math>u</math> не превосходит <math>|subtree(u)| - 1</math>, т.к. наддерево имеет размер меньше, чем поддерево <math>u</math>, а любое поддерево вершины <math>u</math> имеет хотя бы на <math>1</math> вершину меньше (сама вершина <math>u</math>). По индукции получаем, что в любой момент времени размер наддерева вершины v меньше <math>\frac{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])
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''' <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz)

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

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

== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией devide&conqure - деревом отрезков. В предыдущем пункте мы определили статический оналог devide&conqure для дерева. Теперь обобщим этот метод для динамических задач.
{{Определение
|definition=
'''Деревом центроидов (или центроидной декомпозицией)''' дерева <math>t</math> называют дерево <math>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,..., t_k</tex>, а центроиды этих поддеревьев - вершины <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_2,..., t_k</tex>.
}}

{{Лемма
|statement=
Свойства центроидной декомпозиции :
* Глубина дерева центроидов не превосходит <tex>log(n)</tex>.
* Каждая вершина <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>)
|proof=
Действительно, т.к. размер поддерева <math>s</math> каждой вершины <math>c</math> дереве <math>T</math> не превосходит <tex>\frac{|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> т.и т.т., когда c - отец вершины <math>v</math> в дереве центроидов. Т.к. вершина <math>v</math> точно принадлежит дереву <math>T</math> (свойство 2), то она лежит на каком-то пути в дереве <math>T</math>, причем все ее родители (центроиды) ее содержат. А по свойству 1 длина любого вертикального (и даже простого) пути есть <math>O(log(n))</math>, ч.т.д.
}}

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

{{Задача
|definition = Есть страна, <math>n</math> городов которой связаны двустронними дорогами, причем так, чтобы получился минимальный связный граф на <math>n-1</math> ребрах. В каждом городе есть госпиталь, который в каждый момент времени может быть либо открыт, либо закрыт. Дан список из <math>m</math> событий :
* Госпиталь в городе <math>v</math> открылся.
* Госпиталь в городе <math>v</math> закрылся.
* Больной из города <math>v</math> хочет узнать номер ближайшего города, госпиталь которого открыт.
}}

Решение :

Построим центроидную декомпозицию <math>T</math> дерева городов <math>t</math>,

// TODO :: дописать решение (мой код : https://drivenotepad.github.io/app/?state={%22action%22:%22open%22,%22ids%22:[%220Bw29IKNdcznCYnVFbVo2alZiSzA%22]})

== Варианты реализации ==
// TODO :: написать про то, что можно хранить предков (+память О(n), - скорость, - ничего нельзя сделать), а можно для каждой вершины - массив содержащих ее центроидов (+скорость(кэш), +масштабируемость(структуры данных на путях), - память n*logn)

==См. также==

*[[:Дерево_отрезков._Построение|Дерево отрезков]]
*[[:Heavy-light_декомпозиция|Heavy-light декомпозиция]]
*[[:Метод_двоичного_подъема| Метод двоичного подъема]]

== Примечания ==
<references/>

[[Категория:Алгоритмы и структуры данных]]

Centroid decomposition

2017-06-14T10:50:10Z

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

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

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

Задача 1
{{Задача
|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_{i=0}^{n - 1} a_i \leqslant W</tex>.
}}
Задача 2:
{{Задача
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида :
* дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что <tex>|u - v|</tex> минимально возможное.
* дан город <tex>v</tex> и сказано, что больше он не будет принимать больных
* дан город <tex>v</tex> и сказано, что теперь он может принимать больных
}}
Для начала решим обе задачи.
Первая задача решается методом [[Сортировка_слиянием|qevide&conqure (рус. разделяй и властвуй)]] - давайте разделим массив <tex>a[0...n-1]</tex> на 2 массива <tex>a[0...\frac{n}{2} - 1]</tex> и <tex>a[\frac{n}{2}...n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \frac{n}{2}, j \geqslant \frac{n}{2}</tex>. Для этого воспользуемся другой известной техникой - методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_{j=\frac{n}{2}}^{i} a_j</tex> и суффиксных (<tex>suf[i] = \sum_{j=i}^{\frac{n}{2} + 1} a_j</tex>) - для левой. Заведем два указателя (<tex>p_1</tex> и <tex>p_2</tex>). Изначально установим <tex>p_1 = \frac{n}{2} - l + 1, p_2 = \frac{n}{2}</tex>. Пока <tex>p_2 - 1> \frac{n}{2}</tex> и

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

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

== Статическая центроидная декомпозиция ==
Перейдем к обобщению поставленных задач на случай дерева. Начнем, как и полагается, с первой:
{{Задача
|definition = Есть взвешенное дерево <tex>t</tex> из <tex>n</tex> вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа <tex>W >= 0</tex> и <tex>l</tex>. Требуется найти количество пар <tex>(i, j)</tex> вершин дерева, таких что расстояние между ними не превосходит <math>l</math> по числу ребер и не превосходит <math>W</math> по сумме весов.
}}

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

{{Определение
|id=191213
|definition =
'''Центроидом дерева''' (англ. ''centroid'') называется такая вершина <math>v</math> дерева <math>t</math>, после удаления которой дерево разбивается на несколько (<math>k</math>) поддеревьев <tex>t_1, t_2,..., t_k</tex>, таких что для каждого <math>i</math> : <tex>|t_i| \leqslant \frac{n}{2}</tex>, т.е. размер каждого поддерева не превосходит половины размера исходного дерева.
}}
Итак, в случае дерева идея разделяй-и-властвуй из предыдущего пункта будет формулироваться так : найдем центроид (доказательство её существования и алгоритм нахождение см. далее). Предположим, что мы сумели найти центроид за <math>O(n)</math>, где <math>n</math> - размер дерева. Тогда, как и в упрощенной версии задачи - рекурсивно найдем ответ для всех поддеревьев <tex>t_1, t_2,..., 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 * T(n / k) + O(n \cdot log(n))</tex>. Решая это рекурентное соотношение, получим <math>O(n \cdot log(n))</math>.

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

=== Лемма о существовании центроида и алгоритм его нахождения. ===
{{Лемма
|statement=
В любом дереве t существует центроид.
|proof=
Рассмотрим корень дерева <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>\frac{n}{2}</math>, значит максимальное поддерево имеет размер больше чем <math>\frac{n}{2}</math>, т.е. <math>|subtree(u)| > \frac{n}{2}</math>, а значит размер "наддерева" вершины <math>u</math> равен <tex>n - |subtree(u)| < \frac{n}{2}</tex>. При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины <math>u</math> не превосходит <math>|subtree(u)| - 1</math>, т.к. наддерево имеет размер меньше, чем поддерево <math>u</math>, а любое поддерево вершины <math>u</math> имеет хотя бы на <math>1</math> вершину меньше (сама вершина <math>u</math>). По индукции получаем, что в любой момент времени размер наддерева вершины v меньше <math>\frac{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])
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''' <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz)

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

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

== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией devide&conqure - деревом отрезков. В предыдущем пункте мы определили статический оналог devide&conqure для дерева. Теперь обобщим этот метод для динамических задач.
{{Определение
|definition=
""Деревом центроидов (или центроидной декомпозицией)"" дерева <math>t</math> называют дерево <math>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,..., t_k</tex>, а центроиды этих поддеревьев - вершины <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_2,..., t_k</tex>.
}}

{{Лемма
|statement=
Свойства центроидной декомпозиции :
* Глубина дерева центроидов не превосходит <tex>log(n)</tex>.
* Каждая вершина <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>)
|proof=
Действительно, т.к. размер поддерева <math>s</math> каждой вершины <math>c</math> дереве <math>T</math> не превосходит <tex>\frac{|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> т.и т.т., когда c - отец вершины <math>v</math> в дереве центроидов. Т.к. вершина <math>v</math> точно принадлежит дереву <math>T</math> (свойство 2), то она лежит на каком-то пути в дереве <math>T</math>, причем все ее родители (центроиды) ее содержат. А по свойству 1 длина любого вертикального (и даже простого) пути есть <math>O(log(n))</math>, ч.т.д.
}}

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

{{Задача
|definition = Есть страна, <math>n</math> городов которой связаны двустронними дорогами, причем так, чтобы получился минимальный связный граф на <math>n-1</math> ребрах. В каждом городе есть госпиталь, который в каждый момент времени может быть либо открыт, либо закрыт. Дан список из <math>m</math> событий :
* Госпиталь в городе <math>v</math> открылся.
* Госпиталь в городе <math>v</math> закрылся.
* Больной из города <math>v</math> хочет узнать номер ближайшего города, госпиталь которого открыт.
}}

Решение :

Построим центроидную декомпозицию <math>T</math> дерева городов <math>t</math>,

// TODO :: дописать решение (мой код : https://drivenotepad.github.io/app/?state={%22action%22:%22open%22,%22ids%22:[%220Bw29IKNdcznCYnVFbVo2alZiSzA%22]})

== Варианты реализации ==
// TODO :: написать про то, что можно хранить предков (+память О(n), - скорость, - ничего нельзя сделать), а можно для каждой вершины - массив содержащих ее центроидов (+скорость(кэш), +масштабируемость(структуры данных на путях), - память n*logn)

==См. также==

*[[:Дерево_отрезков._Построение|Дерево отрезков]]
*[[:Heavy-light_декомпозиция|Heavy-light декомпозиция]]
*[[:Метод_двоичного_подъема| Метод двоичного подъема]]

== Примечания ==
<references/>

[[Категория:Алгоритмы и структуры данных]]

Centroid decomposition

2017-06-14T10:43:34Z

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

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

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

Задача 1
{{Задача
|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_{i=0}^{n - 1} a_i \leqslant W</tex>.
}}
Задача 2:
{{Задача
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида :
* дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что <tex>|u - v|</tex> минимально возможное.
* дан город <tex>v</tex> и сказано, что больше он не будет принимать больных
* дан город <tex>v</tex> и сказано, что теперь он может принимать больных
}}
Для начала решим обе задачи.
Первая задача решается методом [[Сортировка_слиянием|qevide&conqure (рус. разделяй и властвуй)]] - давайте разделим массив <tex>a[0...n-1]</tex> на 2 массива <tex>a[0...\frac{n}{2} - 1]</tex> и <tex>a[\frac{n}{2}...n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \frac{n}{2}, j \geqslant \frac{n}{2}</tex>. Для этого воспользуемся другой известной техникой - методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_{j=\frac{n}{2}}^{i} a_j</tex> и суффиксных (<tex>suf[i] = \sum_{j=i}^{\frac{n}{2} + 1} a_j</tex>) - для левой. Заведем два указателя (<tex>p_1</tex> и <tex>p_2</tex>). Изначально установим <tex>p_1 = \frac{n}{2} - l + 1, p_2 = \frac{n}{2}</tex>. Пока <tex>p_2 - 1> \frac{n}{2}</tex> и

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

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

== Статическая центроидная декомпозиция ==
Перейдем к обобщению поставленных задач на случай дерева. Начнем, как и полагается, с первой:
{{Задача
|definition = Есть взвешенное дерево <tex>t</tex> из <tex>n</tex> вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа <tex>W >= 0</tex> и <tex>l</tex>. Требуется найти количество пар <tex>(i, j)</tex> вершин дерева, таких что расстояние между ними не превосходит <math>l</math> по числу ребер и не превосходит <math>W</math> по сумме весов.
}}

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

{{Определение
|id=191213
|definition =
'''Центроидом дерева''' (англ. ''centroid'') называется такая вершина <math>v</math> дерева <math>t</math>, после удаления которой дерево разбивается на несколько (<math>k</math>) поддеревьев <tex>t_1, t_2,..., t_k</tex>, таких что для каждого <math>i</math> : <tex>|t_i| \leqslant \frac{n}{2}</tex>, т.е. размер каждого поддерева не превосходит половины размера исходного дерева.
}}
Итак, в случае дерева идея разделяй-и-властвуй из предыдущего пункта будет формулироваться так : найдем центроид (доказательство её существования и алгоритм нахождение см. далее). Предположим, что мы сумели найти центроид за <math>O(n)</math>, где <math>n</math> - размер дерева. Тогда, как и в упрощенной версии задачи - рекурсивно найдем ответ для всех поддеревьев <tex>t_1, t_2,..., 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 * T(n / k) + O(n \cdot log(n))</tex>. Решая это рекурентное соотношение, получим <math>O(n \cdot log(n))</math>.

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

=== Лемма о существовании центроида и алгоритм его нахождения. ===
{{Лемма
|statement=
В любом дереве t существует центроид.
|proof=
Рассмотрим корень дерева <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>\frac{n}{2}</math>, значит максимальное поддерево имеет размер больше чем <math>\frac{n}{2}</math>, т.е. <math>|subtree(u)| > \frac{n}{2}</math>, а значит размер "наддерева" вершины <math>u</math> равен <tex>n - |subtree(u)| < \frac{n}{2}</tex>. При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины <math>u</math> не превосходит <math>|subtree(u)| - 1</math>, т.к. наддерево имеет размер меньше, чем поддерево <math>u</math>, а любое поддерево вершины <math>u</math> имеет хотя бы на <math>1</math> вершину меньше (сама вершина <math>u</math>). По индукции получаем, что в любой момент времени размер наддерева вершины v меньше <math>\frac{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])
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''' <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz)

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

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

== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией devide&conqure - деревом отрезков. В предыдущем пункте мы определили статический оналог devide&conqure для дерева. Теперь обобщим этот метод для динамических задач.
{{Определение
|definition="Деревом центроидов (или центроидной декомпозицией)" дерева <math>t</math> называют дерево <math>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,..., t_k</tex>, а центроиды этих поддеревьев - вершины <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_2,..., t_k</tex>.
}}

{{Лемма
|statement=
Свойства центроидной декомпозиции :
* Глубина дерева центроидов не превосходит <tex>log(n)</tex>.
* Каждая вершина <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>)
|proof=
Действительно, т.к. размер поддерева <math>s</math> каждой вершины <math>c</math> дереве <math>T</math> не превосходит <tex>\frac{|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> т.и т.т., когда c - отец вершины <math>v</math> в дереве центроидов. Т.к. вершина <math>v</math> точно принадлежит дереву <math>T</math> (свойство 2), то она лежит на каком-то пути в дереве <math>T</math>, причем все ее родители (центроиды) ее содержат. А по свойству 1 длина любого вертикального (и даже простого) пути есть <math>O(log(n))</math>, ч.т.д.
}}

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

{{Задача
|definition = Есть страна, <math>n</math> городов которой связаны двустронними дорогами, причем так, чтобы получился минимальный связный граф на <math>n-1</math> ребрах. В каждом городе есть госпиталь, который в каждый момент времени может быть либо открыт, либо закрыт. Дан список из <math>m</math> событий :
* Госпиталь в городе <math>v</math> открылся.
* Госпиталь в городе <math>v</math> закрылся.
* Больной из города <math>v</math> хочет узнать номер ближайшего города, госпиталь которого открыт.
}}

Решение :

Построим центроидную декомпозицию <math>T</math> дерева городов <math>t</math>,

// TODO :: дописать решение (мой код : https://drivenotepad.github.io/app/?state={%22action%22:%22open%22,%22ids%22:[%220Bw29IKNdcznCYnVFbVo2alZiSzA%22]})

== Варианты реализации ==
// TODO :: написать про то, что можно хранить предков (+память О(n), - скорость, - ничего нельзя сделать), а можно для каждой вершины - массив содержащих ее центроидов (+скорость(кэш), +масштабируемость(структуры данных на путях), - память n*logn)

==См. также==

*[[:Дерево_отрезков._Построение|Дерево отрезков]]
*[[:Heavy-light_декомпозиция|Heavy-light декомпозиция]]
*[[:Метод_двоичного_подъема| Метод двоичного подъема]]

== Примечания ==
<references/>

[[Категория:Алгоритмы и структуры данных]]