Centroid decomposition — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Статическая центроидная декомпозиция)
(→‎Лемма о существовании центроида и алгоритм его нахождения.)
Строка 48: Строка 48:
 
В любом дереве t существует центроид.
 
В любом дереве t существует центроид.
 
|proof=
 
|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>, ч.т.д.
+
Рассмотрим корень дерева <math>(r)</math>. Положим изначально <math>v = r</math>. Изначально <math>|subtree(v)| = n</math>. Среди всех детей <math>v</math> выберем вершину  
−
 
 
−
Итак, мы конструктивно доказали существование центроида и привели линейный относительно размера дерева алгоритм его нахождения.
 
 
}}
 
}}
  

Версия 01:42, 14 июня 2017

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

Введение

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

Задача:
Есть массив [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_{i=0}^{n - 1} [a[i]] \leqslant W[/math].

Задача 2:

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

1) дан город [math]v[/math], в котором находится больной и требуется найти такой город [math]u[/math], что [math]abs{u - v}[/math] минимально возможное. 2) дан город [math]v[/math] и сказано, что больше он не будет принимать больных

3) дан город [math]v[/math] и сказано, что теперь он может принимать больных

Для начала решим обе задачи. Первая задача решается методом qevide&conqure (рус. разделяй и властвуй) - давайте разделим массив [math]a[0...n-1][/math] на 2 массива [math]a[0...\frac{n}{2} - 1][/math] и [math]a[\frac{n}{2}...n-1][/math] и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар [math](i, j)[/math], таких что [math]i \lt \frac{n}{2}, j \geqslant \frac{n}{2}[/math]. Для этого воспользуемся другой известной техникой - методом двух указателей. Посчитаем массив префиксных сумм для правой половины [math]pref[i] = \sum_{j=n/2}^{i} [a[j]][/math] и суффиксных ([math]suf[i] = \sum_{j=i}^{n/2 + 1} [a[i]][/math]) - для левой. Заведем два указателя ([math]p1[/math] и [math]p2[/math]). Изначально установим [math]p1 = \frac{n}{2} - l + 1, p2 = \frac{n}{2}[/math]. Пока [math]p2 - 1\gt \frac{n}{2}[/math] и

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

Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию qevide&conqure - дерево отрезков. Построим дерево отрезков, поддерживающее 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(i...j) = 1[/math]). Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков. б) ([math]O(n \cdot log(n)[/math]) Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновоременно и бинарный поиск, и спуск/подъем по дереву.

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

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

Задача:
Есть взвешенное дерево [math]t[/math] из [math]n[/math] вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа [math]W \gt = 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,..., t_k[/math], таких что для каждого [math]i[/math] : [math]|t_i| \leqslant \frac{n}{2}[/math], т.е. размер каждого поддерева не превосходит половины размера исходного дерева.

Итак, в случае дерева идея разделяй-и-властвуй из предыдущего пункта будет формулироваться так : найдем центроид (доказательство её существования и алгоритм нахождение см. далее). Предположим, что мы сумели найти центроид за [math]O(n)[/math], где [math]n[/math] - размер дерева. Тогда, как и в упрощенной версии задачи - рекурсивно найдем ответ для всех поддеревьев [math]t_1, t_2,..., 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].

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

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

{Теорема |statement= В любом дереве t существует центроид. |proof= Рассмотрим корень дерева [math](r)[/math]. Положим изначально [math]v = r[/math]. Изначально [math]|subtree(v)| = n[/math]. Среди всех детей [math]v[/math] выберем вершину }}

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

Варианты реализации

См. также

Примечания

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Centroid_decomposition&oldid=61544»