Корневая декомпозиция. Отложенные операции
В новом видео мы продолжаем изучать корневую декомпозицию и разбираем отложенные операции на группах: как их накапливать, когда применять и как учитывать при вычислении функции на отрезке. На примерах задач «A. Прибавление и минимум» и «B. Умножение и сумма» показываем, как адаптировать структуру под разные типы обновлений и запросов. В конце добавляем ещё один важный тип операций — поиск значения в корневой декомпозиции, начиная с заданной позиции. Тайм-коды: 00:00:00 Начало 00:01:27 Переход к отложенным операциям 00:02:30 Пример задачи: «A. Прибавление и минимум» 00:03:55 Как выполнять прибавление на отрезке в корневой декомпозиции 00:07:10 Как применять отложенные операции при запросах 00:11:10 Другие примеры операций: сумма и присваивание 00:15:15 Пишем решение задачи «A. Прибавление и минимум» 00:29:49 Разбор исходного кода на C++ 00:34:20 Задача «B. Умножение и сумма» 00:37:30 Модифицируем код для поддержки новых операций 00:49:40 Подбираем оптимальный размер группы 00:52:15 Экспериментируем, чтобы ускорить решение 00:59:00 Задача «D. Первый элемент не меньше X - 2»: поиск в корневой декомпозиции 01:04:50 Реализуем поиск в корневой декомпозиции 01:14:20 Ревью функции поиска 01:15:25 Смотрим на другие задачи курса 01:17:30 Завершение
В новом видео мы продолжаем изучать корневую декомпозицию и разбираем отложенные операции на группах: как их накапливать, когда применять и как учитывать при вычислении функции на отрезке. На примерах задач «A. Прибавление и минимум» и «B. Умножение и сумма» показываем, как адаптировать структуру под разные типы обновлений и запросов. В конце добавляем ещё один важный тип операций — поиск значения в корневой декомпозиции, начиная с заданной позиции. Тайм-коды: 00:00:00 Начало 00:01:27 Переход к отложенным операциям 00:02:30 Пример задачи: «A. Прибавление и минимум» 00:03:55 Как выполнять прибавление на отрезке в корневой декомпозиции 00:07:10 Как применять отложенные операции при запросах 00:11:10 Другие примеры операций: сумма и присваивание 00:15:15 Пишем решение задачи «A. Прибавление и минимум» 00:29:49 Разбор исходного кода на C++ 00:34:20 Задача «B. Умножение и сумма» 00:37:30 Модифицируем код для поддержки новых операций 00:49:40 Подбираем оптимальный размер группы 00:52:15 Экспериментируем, чтобы ускорить решение 00:59:00 Задача «D. Первый элемент не меньше X - 2»: поиск в корневой декомпозиции 01:04:50 Реализуем поиск в корневой декомпозиции 01:14:20 Ревью функции поиска 01:15:25 Смотрим на другие задачи курса 01:17:30 Завершение