Отложенное распространение для обновлений диапазонов
Откладывайте обновления целых диапазонов
«Отложенное распространение для обновлений диапазонов» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Проблема обновления диапазона
Что, если запрос требует прибавить 5 к каждому элементу от l до r? Обращение к каждому листу занимает O(n) на одно обновление — слишком медленно для множества обновлений диапазонов. 😰
Идея ленивого распространения
Ленивое распространение позволяет вершине запомнить ожидающее изменение, не передавая его пока потомкам. Работа откладывается до тех пор, пока потомки действительно не понадобятся.
Второй массив для отложенной работы
Вместе с деревом мы храним массив отложенных изменений. Для каждой вершины он хранит обновление, применяемое ко всему диапазону этой вершины, но ещё не переданное потомкам.
lazy = [0] * (4 * n)Применяйте изменение ко всей вершине
Когда обновление полностью покрывает вершину, измените сохранённое в ней значение и добавьте изменение в массив отложенных изменений, после чего остановитесь. Спускаться ниже не нужно.
seg[node] += (r - l + 1) * val
lazy[node] += valПередавайте изменения вниз перед спуском
Перед обращением к потомкам передайте вниз все ожидающие отложенные изменения обоим потомкам. Так потомки будут корректны именно в тот момент, когда Вы их прочитаете.
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0Три случая для каждой вершины
В каждой вершине диапазон запроса либо не пересекается с её диапазоном, либо полностью покрывает его, либо пересекается частично. В этих случаях соответственно пропустите вершину, примените отложенное изменение или рекурсивно обработайте обе половины.
Ленивые обновления остаются логарифмическими
Обновление диапазона затрагивает только O(log n) вершин, поскольку при полном покрытии обработка останавливается раньше. В этом и состоит основная выгода ленивого распространения. ⚡
Запросы тоже нужно проталкивать вниз
Запросы по диапазону также нужно проталкивать вниз перед рекурсивным спуском, чтобы читать актуальные значения дочерних вершин. Если об этом забыть, возникает классическая ошибка ленивого распространения.
Пересчёт после рекурсии
После обновления дочерних вершин пересчитайте родительскую вершину по их значениям. Так подтягивание вверх поддерживает согласованность каждой внутренней вершины с её поддеревом.
seg[node] = seg[2*node] + seg[2*node+1]Присваивание и сложение
Ленивое распространение работает для многих операций, но присваивание и сложение объединяются по-разному. До написания кода определите, как будут объединяться два отложенных обновления.
Когда нужна ленивая обработка
Используйте ленивое распространение только тогда, когда действительно нужны обновления диапазонов. Если нужны только точечные обновления, обычное дерево отрезков проще и достаточно.
Быстрая проверка
Что должно произойти перед рекурсивным переходом к дочерним вершинам?
Итоги: отложенные обновления
Вы изучили ленивое распространение: храните отложенные изменения, проталкивайте их вниз перед спуском, подтягивайте значения вверх после него и получайте обновления диапазонов за O(log n). 🎉
Часто задаваемые вопросы
Урок «Отложенное распространение для обновлений диапазонов» бесплатный?
Да — полный текст урока «Отложенное распространение для обновлений диапазонов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Отложенное распространение для обновлений диапазонов»?
Откладывайте обновления целых диапазонов Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Отложенное распространение для обновлений диапазонов»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Дерево Фенвика для префиксных сумм
- Инверсии с BIT
- Дерево отрезков: построение и запросы
- Отложенное распространение для обновлений диапазонов