Семинар 9. Дерево отрезков

Суббота, 16 ноября 2019
НГУ, ауд. 2128, НГУ, новый корпус

Описание

Интерфейс искомой структуры данных. Решение методом sqrt-декомпозиции за O(sqrt(N)).

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

Видео для студентов заочного отделения: https://my.compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4378/