Segment Tree

Дерево отрезков

Дерево отрезков

Дерево отрезков

Достаточно полезная тема не только в олимпиадном программировании. Если Вы уже осилили двоичные кучи (binary heap), то Вас порадует повторное использование трюка для простого хранения дерева в массиве.
Практически все задачи на дерево отрезков сводятся к необходимости быстрого вычисления некоторой ассоциативной операции для всевозможных диапазонов изменения индексов массива (отрезков массива). Часто к этому требованию добавляется необходимость менять значения элементов массива или их значений на некотором отрезке. Сутью подхода является предварительное построение за [latex]O \left( n \right)[/latex] некоторого дерева, вершины которого хранят значения операции для определенных отрезков массива. Далее используются определенные приёмы нахождения за [latex]O \left( \log n \right)[/latex] значений для тех отрезков, которые не были вычислены предварительно. Пересчет значений узлов при модификации также осуществляется за [latex]O \left( \log n \right)[/latex].
Алгоритм может быть модифицирован для многомерных массивов и более сложных последовательных структур.

Что почитать?

Что порешать?