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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Введение)
(Введение)
Строка 17: Строка 17:
 
Первая задача решается методом [[Сортировка_слиянием|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 >= \frac{n}{2}</tex>. Для этого воспользуемся другой известной техникой - методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_{j=n/2}^{i} [a[j]]</tex> и суффиксных (<tex>suf[i] = \sum_{j=i}^{n/2 + 1} [a[i]]</tex>) - для левой. Заведем два указателя (<tex>p1</tex> и <tex>p2</tex>). Изначально установим <tex>p1 = \frac{n}{2} - l + 1, p2 = \frac{n}{2}</tex>. Пока <tex>p2 - 1> \frac{n}{2}</tex> и <tex>pref[p2] + suf[p1] > W </tex> будем уменьшать <math>p2</math> на <math>1</math>. Если после этого <math>pref[p2] + suf[p1] <= W</math>, то к ответу прибавим <math>(p2 - \frac{n}{2} + 1) * (\frac{n}{2} - p1)</math>, посго, увеличим <math>p1</math> на <math/math>. Так будем делать, пока <math>p1 < \frac{n}{2}</math>. В конце сложим текущий ответ и ответы для половин массива - получим ответ на задачу.
 
Первая задача решается методом [[Сортировка_слиянием|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 >= \frac{n}{2}</tex>. Для этого воспользуемся другой известной техникой - методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_{j=n/2}^{i} [a[j]]</tex> и суффиксных (<tex>suf[i] = \sum_{j=i}^{n/2 + 1} [a[i]]</tex>) - для левой. Заведем два указателя (<tex>p1</tex> и <tex>p2</tex>). Изначально установим <tex>p1 = \frac{n}{2} - l + 1, p2 = \frac{n}{2}</tex>. Пока <tex>p2 - 1> \frac{n}{2}</tex> и <tex>pref[p2] + suf[p1] > W </tex> будем уменьшать <math>p2</math> на <math>1</math>. Если после этого <math>pref[p2] + suf[p1] <= W</math>, то к ответу прибавим <math>(p2 - \frac{n}{2} + 1) * (\frac{n}{2} - p1)</math>, посго, увеличим <math>p1</math> на <math/math>. Так будем делать, пока <math>p1 < \frac{n}{2}</math>. В конце сложим текущий ответ и ответы для половин массива - получим ответ на задачу.
  
Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию qevide&conqure - [[Дерево_отрезков._Построение|дерево отрезков]]. Построим дерево отрезков, поддерживающее 2 вида запросов : присвоение в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив <math>b[]</math>, такой что <tex>b[i] = 0</tex>, если в i-м городе принимает госпиталь и <tex>b[i] = 1</tex> иначе. Когда в каком-то городе открывается/закрывается госпиталь - делаем запрос на изменение в дереве отрезков. Когда требуется узнать ближайщий госпиталь к <math>i</math>-му городу, можно воспользоваться одной из следующих идей :
+
Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию qevide&conqure - [[Дерево_отрезков._Построение|дерево отрезков]]. Построим дерево отрезков,
а) (<tex>O(n*log^2(n)</tex>) Бинарным поиском ищем ближайший слева и ближайший справа к i-му городу госпиталь (такой город <math>j</math>, что <math>min(i...j) = 1</math>). Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков. 
 
б) (<tex>O(n*log(n)</tex>) Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновоременно и бинарный поиск, и спуск/подъем по дереву.
 
  
 
== Статическая центроидная декомпозиция ==
 
== Статическая центроидная декомпозиция ==

Версия 00:13, 14 июня 2017

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

Введение

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

Задача:
Есть массив [math]a[][/math] положительных целых чисел из [math]n[/math] элементов и числа [math]W \gt = 0[/math] и [math]l[/math] . Требуется найти количество пар [math](i, j)[/math] индексов массива, таких что [math]|j - i| \lt = l [/math] и [math]\sum_{i=0}^{n - 1} [a[i]] \lt = 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 \gt = \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] \lt = 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 - дерево отрезков. Построим дерево отрезков,

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

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

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

См. также

Примечания