Segment Tree

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

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

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

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

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

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

Мазурок Игорь Евгеньевич

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах
Мазурок Игорь Евгеньевич

Latest posts by Мазурок Игорь Евгеньевич (see all)