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
