Дерево отрезков
Дерево отрезков
Дерево отрезков (Segment Tree) — структура данных для быстрого ответа на запросы на подотрезке массива и обновлений элементов.
Обычно используется для запросов вида:
- сумма на отрезке
- минимум / максимум на отрезке
- и другие ассоциативные операции
Идея
Есть массив .
Мы строим бинарное дерево, где:
- каждый узел хранит значение для некоторого отрезка
- корень хранит значение для всего массива