Centroid decomposition — различия между версиями
(Новая страница: «Centroid decomposition (рус. центроидная декомпозиция) - это структура данных, позволяющая отвечать...») |
(→См. также) |
||
| Строка 17: | Строка 17: | ||
*[[:Дерево_отрезков._Построение]] | *[[:Дерево_отрезков._Построение]] | ||
*[[:Heavy-light_декомпозиция]] | *[[:Heavy-light_декомпозиция]] | ||
| − | *[[:Метод_двоичного_подъема]] | + | *[[:Метод_двоичного_подъема| Метод двоичного подъема]] |
== Примечания == | == Примечания == | ||
Версия 23:05, 13 июня 2017
Centroid decomposition (рус. центроидная декомпозиция) - это структура данных, позволяющая отвечать на запросы на дереве. Чаще всего это запросы, связанные с нахождением функции на вершинах, связанных неравенством на расстояние между ними в дереве. Также иногда применяется для запросов на путях в дереве.
Содержание
Введение
Рассмотрим задачу на обычном массиве:
| Задача: |
| Есть прямая дорога, на которой расположены городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида : дан город , в котором находится больной и требуется найти такой город , что минимально возможное. |
