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

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
(Введение)
Строка 2: Строка 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> минимально возможное.
 +
}}
 +
 +
{{Задача 2
 +
|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:27, 13 июня 2017

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

Введение

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

Шаблон:Задача 2

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

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

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

См. также

Примечания