Алгоритмы и структуры данных (основной поток) 8. Дерево отрезков

Таймкоды: 00:00 Введение 3:15 Описание структуры на примере n = 8 11:10 Нумерация вершин ~ 14:30 В дереве не больше 4n вершин 20:10 Функция Update 25:35 Функция GetSum 32:05 Асимптотика GetSum — O(log n) — “Боковые“ случаи — 38:55 Общий случай 42:05 Задача 2 45:25 Бинарный спуск 54:00 Задача 3 — “отложенные операции“ 1:01:00 Процедура Push 1:13:00 Суть отложенных операций 1:14:00 Задача 4 — “кол-во эл., меньших Х на подотрезке“ ~1:19:00 Построение дерева, Merge sort 1:22:10 Избавление от log^2 n. Fractional Cascading Лектор: Степанов Илья Даниилович Оператор: Марк Захаров Монтажер: Чегодаев Алексей Плейлист: