Лекция, Корневая Декомпозиция, 2024-07-13

В этом видео вы узнаете, что такое корневая декомпозиция, какие операции можно выполнять с её помощью (в том числе, и изменения на отрезке), а также вы узнаете как её реализовать и где найти задачи для её тестирования

00:00:00 Стартуем
00:00:50 Задачи на отрезках
00:05:30 Корневая декомпозиция
00:15:45 Корневая оптимизация в математике
00:22:40 Структура корневой декомпозиции
00:28:45 Минимум на отрезке и присваивание по индексу
00:31:55 Минимум и его количество
00:34:55 Изменение на отрезке
00:47:45 Преимущество корневой над деревом отрезков
00:56:30 Поиск в корневой декомпозиции
01:10:45 Реализация корневой декомпозиции, обновление по индексу
01:27:27 Вычисление оптимального размера группы
01:33:00 Делаем код более шаблонным
01:36:00 Реализация обновления на отрезке
01:52:20 Фиксим баги
02:00:00 В чём был баг и что исправили
02:08:04 Тестируем время работы на миллионе элементов и 500 тысячах запросов!
02:26:45 Выводы и прощание