Семинар 9. Дерево отрезков (Алгоритмы и структуры данных, часть 1)

Интерфейс искомой структуры данных. Решение методом sqrt-декомпозиции за O(sqrt(N)). Дерево отрезков. Структура дерева. Использование нумерации кучи (если N = 2^p). Хранение в узлах частичных ответов. Рекурсивные и итеративные алгоритмы Set и Query. Время работы. Модификации на отрезке. Хранение в узлах отложенных модификаций. Актуализация вершин в рекурсивном обходе = опускание модификации. Реализуемость произвольного набора запросов и модификаций на отрезке: требования. Примеры: { =, *=, min(a)}, { =, su