Centroid decomposition

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

Введение

Рассмотрим 2 задачи на обычном массиве (в дальнейшем мы будем их обобщать на случай дерева):

Задача:

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

Задача:

Есть массив [math]a[][/math] из [math]n[/math] элементов и числа [math]W[/math] и [math]l[/math] . Требуется найти количество пар [math](i, j)[/math] индексов массива, таких что [math]|j - i| \lt = l [/math] и [math]\sum_{i=0}^{n - 1} [a[i]] \lt = W[/math].

См. также

• Дерево отрезков
• Heavy-light декомпозиция
• Метод двоичного подъема