Centroid decomposition

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Введение

Рассмотрим задачу на обычном массиве:

Задача:
Есть прямая дорога, на которой расположены [math]n[/math] городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида : дан город [math]v[/math], в котором находится больной и требуется найти такой город [math]u[/math], что [math]abs{u - v}[/math] минимально возможное.


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

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

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

См. также

Примечания