Где применяется
1. Задача
Дерево отрезков из прошлого урока меняло один элемент за раз. Ты записывал новое значение в лист и поднимался по единственному пути до корня, пересчитывая каждого предка. Это точечное обновление: изменилась одна позиция, цена O(log n).
Теперь изменение касается целого участка: «прибавить 3 к каждому элементу в [l, r]». Бронь занимает места с 41 по 80, и счётчик каждого из этих 40 мест растёт на единицу. Если делать это точечными обновлениями, получится 40 подъёмов по дереву. Отрезок из миллиона позиций даст миллион подъёмов. Изменение отрезка снова стоит O(длина отрезка), и дерево ничего не выиграло.
Нужно, чтобы «прибавить delta ко всему [l, r]» стоило те же O(log n), что и запрос. Для этого спуск останавливается на узлах, отрезок которых целиком внутри [l, r]. Изменение записывается прямо на них и не спускается до каждого листа.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где прибавляют к целому отрезку или переворачивают его, а потом спрашивают сумму или максимум на отрезке. На LeetCode ленивое дерево нужно редко, ведь когда все обновления идут до запросов, проще массив разностей из урока 27. Оно окупается, когда обновления и запросы перемешаны.
Прибавления на отрезках, а потом одно чтение каждого счётчика мест. Ленивое дерево проходит, а массив разностей из урока 27 делает это за O(n).
Переворот на отрезке от l до r превращает число единиц в длину минус это число, так что храни счётчики и отложенный переворот в каждом узле.
Сожми края квадратов в позиции. Каждый квадрат читает максимум высоты на своём отрезке и ставит весь отрезок в новую высоту, так что отложенная метка хранит значение для записи там, где в уроке она хранит прибавку.