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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Введение)
(Введение)
Строка 3: Строка 3:
 
== Введение ==
 
== Введение ==
 
Рассмотрим 2 задачи на обычном массиве (в дальнейшем мы будем их обобщать на случай дерева):
 
Рассмотрим 2 задачи на обычном массиве (в дальнейшем мы будем их обобщать на случай дерева):
{{Задача 1
+
{{Задача
 
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида : дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что <tex>abs{u - v}</tex> минимально возможное.
 
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида : дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что <tex>abs{u - v}</tex> минимально возможное.
 +
}}
 +
 +
 +
{{Задача
 +
|definition = Есть массив <tex>a[]</tex> из <tex>n</tex> элементов и числа <tex>W</tex> и <tex>l</tex> . Требуется найти количество пар <tex>(i, j)</tex> индексов массива, таких что <tex>|j - i| <= l </tex> и <tex>\sum_{i=0}^{n - 1} [a[i]] <= W</tex>.
 
}}
 
}}
  

Версия 23:28, 13 июня 2017

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

Введение

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

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



Задача:
Есть массив [math]a[][/math] из [math]n[/math] элементов и числа [math]W[/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].


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

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

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

См. также

Примечания