186
правок
Изменения
Новая страница: «Centroid decomposition (рус. центроидная декомпозиция) - это структура данных, позволяющая отвечать...»
Centroid decomposition (рус. центроидная декомпозиция) - это структура данных, позволяющая отвечать на запросы на дереве. Чаще всего это запросы, связанные с нахождением функции на вершинах, связанных неравенством на расстояние между ними в дереве. Также иногда применяется для запросов на путях в дереве.
== Введение ==
Рассмотрим задачу на обычном массиве:
{{Задача
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида : дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что <tex>abs{u - v}</tex> минимально возможное.
}}
== Статическая центроидная декомпозиция ==
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
== Варианты реализации ==
==См. также==
*[[:Дерево_отрезков._Построение]]
*[[:Heavy-light_декомпозиция]]
*[[:Метод_двоичного_подъема]]
== Примечания ==
<references/>
[[Категория:Алгоритмы и структуры данных]]
== Введение ==
Рассмотрим задачу на обычном массиве:
{{Задача
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида : дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что <tex>abs{u - v}</tex> минимально возможное.
}}
== Статическая центроидная декомпозиция ==
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
== Варианты реализации ==
==См. также==
*[[:Дерево_отрезков._Построение]]
*[[:Heavy-light_декомпозиция]]
*[[:Метод_двоичного_подъема]]
== Примечания ==
<references/>
[[Категория:Алгоритмы и структуры данных]]
