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