Корневая декомпозиция. Разбор задач

В этом видео мы разбираем несколько классических задач на корневую декомпозицию: НОД на отрезках, сумма, минимум, максимум и его индекс, прибавление на отрезке и получение значения элемента по индексу. Показываем два секретных способа прибавления без ленивых обновлений. Также пишем полноценную структуру на C++ с конструктором и методами. Тайм-коды: 00:00:00 Повторение материала с прошлого занятия 00:04:00 Задача "A. НОД на отрезках" 00:08:50 Задача "B. RSQ с изменением элемента" 00:14:10 Задача "C. RMQ с изменением элемента" 00:21:29 Задача "E. Range Maximum Query": ищем максимум и его индекс 00:30:55 Начало задачи "F. Дерево с изменением отрезка" 00:32:38 Разбираем, как присваивать по индексу, если умеем только прибавлять 00:35:20 Как прибавлять на отрезке (без ленивых обновлений) 00:46:22 Реализация корневой декомпозиции в виде структуры в C++ с конструктором и методами 01:03:15 Прибавление на отрезке через разностный массив 01:15:18 Разбираем получившийся код решения задачи "F. Дерево с изменением отрезка" 01:22:08 Завершение