Лекция: Sparse Table, binary lifting, бинарный поиск, задачи

Сегодня мы собрались, чтобы разобраться, что такое Sparse Table и binary lifting. Попутно мы разобрали кучу задач (5-6), в которых можно применить Sparse Table, хоть и не обязательно это делать.

Материалы занятия (задачи и исходники): https://docs.google.com/document/d/1u...

00:00:00 Введение
00:03:00 Что такое Sparse Table
00:09:00 Вычисление функции на отрезке за O(1)
00:11:03 Необходимая память O(n log(n))
00:16:20 Максимальная степень двойки до n за O(1) с предподсчётом и без
00:20:50 Построение Sparse Table
00:24:26 Битовый сдвиг влево = степень двойки
00:27:40 Задача A. Ultra Sparse Table
00:32:30 Реализуем построение Sparse Table
00:37:00 Реализуем запрос к Sparse Table
00:39:30 Вопросы по числу операций за секунду
00:42:30 Задача: ближайший больший элемент
00:46:25 Бинарный поиск + Sparse Table
00:49:45 Ещё есть другое решение, за линию, со стэком
00:51:35 Вопросы про бинпоиск
00:52:20 Реализуем бинпоиск для Sparse Table
00:56:35 Задача F. Несбалансированный массив
01:05:25 Исходный код решения задачи
01:06:20 Как убрать (учесть) повторы из массива в этой задаче
01:11:15 Продолжаем разбирать исходный код задачи
01:14:30 Что такое лямбда-функции и компараторы
01:27:20 Binary lifting (двоичный спуск)
01:35:20 Реализация binary lifting на плюсах
01:41:30 Смотрим откуда задача взялась
01:43:20 Задача E. И снова карточная игра
01:46:00 Первое решение: теория чисел, факторизация, два указателя
01:52:45 Объясняю первое решение на пальцах (на примере)
01:55:30 Подрубаем метод двух указателей в первом решении
01:56:45 Второе решение: Sparse Table + binary lifting
02:04:45 Почему не работают префикс-произведения: модуль не простой
02:06:10 Вычисление функции за O(log(n)) из-за пересечений
02:09:20 Итоговая асимптотика второго решения
02:10:50 Смотрим исходный код решения
02:15:36 Реализация шаблонной функции для Sparse Table
02:19:20 Реализация шаблонной структуры Sparse Table
02:24:20 Задача C. Новогоднее дерево
02:24:40 Используем поиск минимума и его позиции
02:27:40 Строим дерево за квадрат
02:29:55 Ускоряем с помощью сортировки и Sparse Table
02:34:50 Вопрос: третье решение через LCA
02:39:10 Идея по двумерной Sparse Table в задаче L. OpenStreetMap
02:42:00 Вопрос: кто такой tourist?
02:45:30 Смотрим исходный код C. Новогоднее дерево
02:51:30 Прощаемся