Алгоритмы и структуры данных (основной поток) 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

23.10.2024

Лектор: Степанов Илья Даниилович

Оператор: Марк Захаров
Монтажер: Чегодаев Алексей