Дерево отрезков с ленивыми операциями: присвоение и прибавление на отрезке
Lazy propagation в дереве отрезков: как хранить отложенные операции, проталкивать их детям и совмещать присвоение с прибавлением. Сумма, минимум, Falling Squares, код на Python.
Коротко
| Что | Как |
|---|---|
| Задача | Изменять целый отрезок массива (прибавить , присвоить ) и отвечать на запросы суммы, минимума, максимума на отрезке |
| Без ленивости | Изменение отрезка длины — это точечных обновлений, |
| С ленивостью | И изменение, и запрос — , память |
| Главная идея | Если отрезок узла целиком внутри изменения, обновляем значение узла и записываем «долг» детям, а вниз не идём |
| Три функции | apply — применить операцию к узлу, push — отдать долг детям, pull — пересчитать узел из детей |
- Отложенная операция в узле уже учтена в значении самого узла, но ещё не применена к его потомкам.
- Перед тем как спуститься в детей (и при изменении, и при запросе), долг проталкивается вниз.
- Если в дереве живут два вида операций, например присвоение и прибавление, нужно продумать, как они складываются. В этом месте чаще всего и ошибаются.
С чего начинаем
Базовое дерево отрезков (построение, точечное обновление, запрос суммы и минимума) подробно разобрано в статье «Дерево отрезков». Там же есть первая версия ленивого прибавления для суммы. Здесь продолжим с этого места: соберём общий шаблон, на котором держатся все ленивые деревья, и разберём случаи, на которых обычно спотыкаются, — присвоение, минимум и смесь нескольких операций.
Обозначения те же, что в базовой статье: узел node отвечает за отрезок [l, r], его дети — 2*node (отрезок [l, m]) и 2*node + 1 (отрезок [m+1, r]), где m = (l + r) // 2. Корень — узел 1 с отрезком [0, n-1], массивы размера 4n.
Зачем нужна ленивость
Пусть пришёл запрос «прибавить 5 ко всем элементам с 0 по ». Обычное дерево отрезков умеет только точечное обновление, поэтому придётся обновить листьев и пересчитать всех их предков. Это на один запрос, хуже наивного массива.
Заметим: запрос суммы или минимума на большом отрезке почти никогда не спускается до листьев. Он собирает ответ из крупных узлов. Значит, и изменение можно остановить на тех же крупных узлах: поправить их значения, а детям оставить записку «вас тоже нужно увеличить на 5, сделаю, когда понадобится». Если в этих детей потом никто не зайдёт, работа так и не понадобится.
Это и есть ленивое (отложенное) распространение, lazy propagation.
Инвариант
Всё держится на одном правиле. Для любого узла:
Значение узла верное с учётом всех операций, которые до него дошли. Отложенная операция узла (тег) — это то, что ещё нужно применить к его детям.
Отсюда следуют три действия:
apply(node, op)— применить операцию к узлу целиком: пересчитать его значение (сумму, минимум) и скомбинироватьopс его тегом. Детей не трогаем.push(node)— если у узла есть тег, вызватьapplyдля обоих детей с этим тегом и очистить тег.pull(node)— пересчитать значение узла из значений детей. Это обычная операция базового дерева.
Рекурсивные update и query устроены одинаково:
- Отрезок узла не пересекается с запросом — выйти.
- Отрезок узла целиком внутри запроса — для
updateвызватьapply, дляqueryвернуть значение узла. Вниз не идём. - Иначе —
push, рекурсия в обоих детей, и дляupdateещёpull.
Шаг 3 — ключевой. push стоит перед спуском, потому что дети должны стать «честными» до того, как мы их прочитаем или изменим. pull стоит после, потому что дети изменились.
Прибавление на отрезке и минимум
Самый простой случай. Тег — число, которое нужно прибавить ко всем элементам отрезка. Если ко всем элементам прибавить , минимум тоже вырастет ровно на , причём длина отрезка тут не важна.
class AddMinTree: """Прибавление на отрезке, минимум на отрезке.""" def __init__(self, arr): self.n = len(arr) self.mn = [0] * (4 * self.n) self.add = [0] * (4 * self.n) # отложенное прибавление self._build(1, 0, self.n - 1, arr) def _build(self, node, l, r, arr): if l == r: self.mn[node] = arr[l] return m = (l + r) // 2 self._build(2 * node, l, m, arr) self._build(2 * node + 1, m + 1, r, arr) self.mn[node] = min(self.mn[2 * node], self.mn[2 * node + 1]) def _apply(self, node, v): # применяем операцию к узлу целиком: значение обновили, детям — потом self.mn[node] += v self.add[node] += v def _push(self, node): if self.add[node]: self._apply(2 * node, self.add[node]) self._apply(2 * node + 1, self.add[node]) self.add[node] = 0 def update(self, ql, qr, v, node=1, l=0, r=None): if r is None: r = self.n - 1 if qr < l or r < ql: return if ql <= l and r <= qr: self._apply(node, v) return self._push(node) m = (l + r) // 2 self.update(ql, qr, v, 2 * node, l, m) self.update(ql, qr, v, 2 * node + 1, m + 1, r) self.mn[node] = min(self.mn[2 * node], self.mn[2 * node + 1]) def query(self, ql, qr, node=1, l=0, r=None): if r is None: r = self.n - 1 if qr < l or r < ql: return float('inf') if ql <= l and r <= qr: return self.mn[node] self._push(node) m = (l + r) // 2 return min(self.query(ql, qr, 2 * node, l, m), self.query(ql, qr, 2 * node + 1, m + 1, r)) t = AddMinTree([5, 3, 8, 6, 1, 4]) print(t.query(0, 3)) # 3 t.update(1, 4, 10) # [5, 13, 18, 16, 11, 4] print(t.query(0, 3)) # 5 print(t.query(2, 5)) # 4
Два прибавления подряд складываются просто: add[node] += v. Для операций, которые так легко не складываются, понадобится больше аккуратности — об этом ниже.
Если нужна сумма вместо минимума, apply должен знать длину отрезка: сумма растёт на . Поэтому в версии с суммой apply и push принимают ещё l и r. Длину можно и хранить в отдельном массиве, если не хочется передавать границы.
Присвоение на отрезке и сумма
Теперь операция «сделать все элементы отрезка равными ». Чем она отличается от прибавления:
- Новое присвоение затирает старое. Комбинация тегов — не сумма, а замена:
tag = x. - Нужен признак «тега нет». Ноль не подходит: присвоить 0 — нормальная операция. Нужен отдельный маркер, в Python удобно
None. - Сумма считается заново, а не корректируется: .
class AssignSumTree: """Присвоение на отрезке, сумма на отрезке.""" def __init__(self, arr): self.n = len(arr) self.sm = [0] * (4 * self.n) self.val = [None] * (4 * self.n) # None — «присвоения нет» self._build(1, 0, self.n - 1, arr) def _build(self, node, l, r, arr): if l == r: self.sm[node] = arr[l] return m = (l + r) // 2 self._build(2 * node, l, m, arr) self._build(2 * node + 1, m + 1, r, arr) self.sm[node] = self.sm[2 * node] + self.sm[2 * node + 1] def _apply(self, node, l, r, x): self.sm[node] = x * (r - l + 1) # сумма зависит от длины отрезка self.val[node] = x # новое присвоение затирает старое def _push(self, node, l, r): if self.val[node] is not None: m = (l + r) // 2 self._apply(2 * node, l, m, self.val[node]) self._apply(2 * node + 1, m + 1, r, self.val[node]) self.val[node] = None def assign(self, ql, qr, x, node=1, l=0, r=None): if r is None: r = self.n - 1 if qr < l or r < ql: return if ql <= l and r <= qr: self._apply(node, l, r, x) return self._push(node, l, r) m = (l + r) // 2 self.assign(ql, qr, x, 2 * node, l, m) self.assign(ql, qr, x, 2 * node + 1, m + 1, r) self.sm[node] = self.sm[2 * node] + self.sm[2 * node + 1] def query(self, ql, qr, node=1, l=0, r=None): if r is None: r = self.n - 1 if qr < l or r < ql: return 0 if ql <= l and r <= qr: return self.sm[node] self._push(node, l, r) m = (l + r) // 2 return (self.query(ql, qr, 2 * node, l, m) + self.query(ql, qr, 2 * node + 1, m + 1, r)) t = AssignSumTree([1, 2, 3, 4, 5, 6, 7, 8]) t.assign(2, 5, 0) # [1, 2, 0, 0, 0, 0, 7, 8] print(t.query(0, 7)) # 18 t.assign(4, 7, 1) # [1, 2, 0, 0, 1, 1, 1, 1] print(t.query(3, 6)) # 3
Разбор по шагам
Проследим, что происходит в дереве на этом примере. Массив из 8 элементов, корень отвечает за [0, 7].
assign(2, 5, 0). Корень [0, 7] пересекается частично, спускаемся. В левой половине [0, 3] — снова частично: [0, 1] вне запроса, а [2, 3] целиком внутри. В правой [4, 7]: [4, 5] целиком внутри, [6, 7] вне. Итого apply вызван ровно для двух узлов, [2, 3] и [4, 5]: их суммы стали 0, теги — 0. Листья 2, 3, 4, 5 не тронуты, в них по-прежнему лежат старые значения. На обратном пути pull пересчитал [0, 3], [4, 7] и корень: сумма 18.
assign(4, 7, 1). Корень частично, спускаемся вправо: [4, 7] целиком внутри. apply ставит ему сумму 4 и тег 1. При этом у его ребёнка [4, 5] всё ещё висит устаревший тег 0, но это не страшно: родительский тег новее и при проталкивании его затрёт.
query(3, 6). Слева доходим до [2, 3], он пересекается частично, поэтому push отдаёт тег 0 листьям 2 и 3. Лист 3 возвращает 0. Справа [4, 7] пересекается частично, push отдаёт тег 1 детям [4, 5] (затирая устаревший 0) и [6, 7]. Узел [4, 5] целиком внутри — возвращает 2. Узел [6, 7] частично — ещё один push, лист 6 возвращает 1. Ответ .
Обратите внимание: в листьях 4 и 5 до сих пор лежат исходные 5 и 6. Это нормально: за верное значение отвечает узел [4, 5], а до листьев никто не дошёл. Ленивое дерево не обязано держать листья в актуальном состоянии.
Присвоение и прибавление в одном дереве
Самый интересный случай: дерево поддерживает обе операции и отвечает сразу на сумму, минимум и максимум. Теперь тег должен описывать любую последовательность присвоений и прибавлений одной записью.
Посмотрим, во что сворачивается цепочка операций над одним элементом:
- «прибавить 3, прибавить 4» — это «прибавить 7»;
- «прибавить 3, присвоить 10» — это «присвоить 10»: всё, что было до присвоения, неважно;
- «присвоить 10, прибавить 4» — это «присвоить 14», или, что то же самое, «присвоить 10, потом прибавить 4».
Значит, любая цепочка сводится к паре (set, add) с фиксированным порядком: сначала присвоить set (если он есть), потом прибавить add. Правила комбинации:
| Пришла операция | Новый тег |
|---|---|
| присвоить | (x, 0) — старый тег полностью забыт |
| прибавить | (set, add + v) — set не меняется |
В push порядок тот же: сначала передаём детям присвоение, затем прибавление.
class LazySegTree: """Присвоение и прибавление на отрезке; сумма, минимум и максимум на отрезке. Отложенная операция узла — пара (set, add): «сначала присвоить set (если он не None), потом прибавить add». """ def __init__(self, arr): self.n = len(arr) size = 4 * self.n self.sm = [0] * size self.mn = [0] * size self.mx = [0] * size self.set = [None] * size self.add = [0] * size self._build(1, 0, self.n - 1, arr) def _pull(self, node): a, b = 2 * node, 2 * node + 1 self.sm[node] = self.sm[a] + self.sm[b] self.mn[node] = min(self.mn[a], self.mn[b]) self.mx[node] = max(self.mx[a], self.mx[b]) def _build(self, node, l, r, arr): if l == r: self.sm[node] = self.mn[node] = self.mx[node] = arr[l] return m = (l + r) // 2 self._build(2 * node, l, m, arr) self._build(2 * node + 1, m + 1, r, arr) self._pull(node) def _apply_set(self, node, l, r, x): self.sm[node] = x * (r - l + 1) self.mn[node] = self.mx[node] = x self.set[node] = x self.add[node] = 0 # присвоение отменяет все прибавления до него def _apply_add(self, node, l, r, v): self.sm[node] += v * (r - l + 1) self.mn[node] += v self.mx[node] += v self.add[node] += v # set не трогаем: «присвоить, потом прибавить» def _push(self, node, l, r): m = (l + r) // 2 for child, cl, cr in ((2 * node, l, m), (2 * node + 1, m + 1, r)): if self.set[node] is not None: self._apply_set(child, cl, cr, self.set[node]) if self.add[node]: self._apply_add(child, cl, cr, self.add[node]) self.set[node] = None self.add[node] = 0 def _update(self, ql, qr, kind, x, node, l, r): if qr < l or r < ql: return if ql <= l and r <= qr: if kind == 'set': self._apply_set(node, l, r, x) else: self._apply_add(node, l, r, x) return self._push(node, l, r) m = (l + r) // 2 self._update(ql, qr, kind, x, 2 * node, l, m) self._update(ql, qr, kind, x, 2 * node + 1, m + 1, r) self._pull(node) def assign(self, l, r, x): self._update(l, r, 'set', x, 1, 0, self.n - 1) def add_range(self, l, r, v): self._update(l, r, 'add', v, 1, 0, self.n - 1) def query(self, ql, qr, node=1, l=0, r=None): """Возвращает (сумма, минимум, максимум) на [ql, qr].""" if r is None: r = self.n - 1 if qr < l or r < ql: return 0, float('inf'), float('-inf') if ql <= l and r <= qr: return self.sm[node], self.mn[node], self.mx[node] self._push(node, l, r) m = (l + r) // 2 s1, mn1, mx1 = self.query(ql, qr, 2 * node, l, m) s2, mn2, mx2 = self.query(ql, qr, 2 * node + 1, m + 1, r) return s1 + s2, min(mn1, mn2), max(mx1, mx2) t = LazySegTree([2, 7, 1, 8, 2, 8]) t.add_range(0, 5, 1) # [3, 8, 2, 9, 3, 9] t.assign(1, 3, 5) # [3, 5, 5, 5, 3, 9] t.add_range(2, 4, -2) # [3, 5, 3, 3, 1, 9] print(t.query(0, 5)) # (24, 1, 9) print(t.query(1, 3)) # (11, 3, 5)
Все три класса из статьи сверены с наивным массивом на нескольких сотнях случайных тестов: случайные длины до 30, по 60 случайных операций. Такой стресс-тест стоит написать для любого своего ленивого дерева, это пять минут работы, а ошибки в порядке тегов иначе найти очень трудно.
Почему это работает: общий взгляд
За кодом стоит небольшая алгебра. Ленивое дерево корректно, если выполнены три условия:
- Значения узлов объединяются ассоциативно: сумма, минимум, максимум, НОД.
- Операция применяется к агрегату узла без знания отдельных элементов. Прибавление к минимуму — да: . Присвоение к сумме — да, если известна длина. А вот «взять каждый элемент по модулю 3» к сумме — нет: сумма остатков не выражается через остаток суммы.
- Две операции подряд сворачиваются в одну операцию того же вида. Для пары «присвоение + прибавление» это тег
(set, add). Для «умножить на и прибавить » — тег , композиция двух таких функций снова имеет вид .
Если любое из условий нарушено, ленивое дерево напрямую не построить. Иногда помогает расширить данные в узле: например, для операции «развернуть биты на отрезке» (0 ↔ 1) с запросом суммы достаточно знать длину, а для «умножить на » с запросом максимума нужно хранить и минимум, потому что после смены знака минимум становится максимумом.
Пример задачи: Falling Squares
LeetCode 699. На прямую по одному падают квадраты: [left, side] — левая граница и сторона. Квадрат падает, пока не ляжет на пол или на уже упавший квадрат. После каждого падения нужно вернуть высоту самой высокой стопки.
Переформулируем на языке отрезков. Храним высоту над каждой точкой. Квадрат занимает отрезок [left, left + side). Он ляжет на максимум высот на этом отрезке, и после этого весь отрезок станет высотой max + side. То есть нужны:
- запрос максимума на отрезке;
- присвоение на отрезке.
Это ровно LazySegTree выше. Присвоение здесь корректно: новая высота не меньше любой старой на этом отрезке. Координаты до , поэтому сначала сжимаем их, как в задачах сканирующей прямой.
def falling_squares(positions): # сжимаем координаты: клетка i — полуинтервал [xs[i], xs[i+1]) xs = sorted({x for left, side in positions for x in (left, left + side)}) idx = {x: i for i, x in enumerate(xs)} tree = LazySegTree([0] * (len(xs) - 1)) best, res = 0, [] for left, side in positions: l, r = idx[left], idx[left + side] - 1 top = tree.query(l, r)[2] + side # максимум под квадратом + его сторона tree.assign(l, r, top) best = max(best, top) res.append(best) return res print(falling_squares([[1, 2], [2, 3], [6, 1]])) # [2, 5, 5] print(falling_squares([[100, 100], [200, 100]])) # [100, 100]
Тонкость — полуинтервалы. Квадраты [100, 200) и [200, 300) только касаются, и второй не должен лечь на первый. Поэтому в сжатых координатах отрезок квадрата заканчивается на idx[left + side] - 1: клетка с индексом idx[left + side] начинается ровно там, где квадрат кончается. Решение проверено на примерах из условия и на случайных тестах против симуляции «в лоб».
Сложность: для квадратов. При ограничении LeetCode в 1000 квадратов проходит и решение за , но на собеседовании дерево отрезков — естественный follow-up.
Сложность
| Операция | Время | Память |
|---|---|---|
| Построение | , массивы размера | |
| Изменение на отрезке | стек рекурсии | |
| Запрос на отрезке | стек рекурсии |
Почему , если push вызывается при каждом спуске? На каждом уровне дерева запрос «частично» задевает не больше двух узлов: тех, где проходят границы ql и qr. Только они вызывают push и рекурсию, а у каждого из них не больше двух детей. Получается не больше четырёх посещённых узлов на уровень, а push работает за . Уровней .
На практике рекурсивное ленивое дерево в Python медленное: случайных операций на массиве из элементов занимают несколько секунд. Для олимпиадных ограничений обычно пишут на C++ или используют нерекурсивную реализацию. На собеседовании скорость Python не проблема, там важнее правильность.
Типичные ошибки
- Нет
pushвquery. Кажется, что запрос ничего не меняет и проталкивать нечего. Но безpushдети содержат устаревшие значения, и ответ будет неверным, как только запрос задевает узел с тегом частично. pushпосле рекурсии, а не до. Дети читаются до того, как получили долг.- Забыт
pullпосле рекурсии вupdate. Дети обновились, а родитель хранит старое значение. - Ноль как «нет присвоения». Присвоить 0 — легальная операция. Нужен
Noneили отдельный флаг. - Сумма без длины. При прибавлении сумма растёт на , а не на . При присвоении равна . С минимумом и максимумом длина не нужна, поэтому ошибка всплывает только при переходе к сумме.
- Неправильная композиция тегов. Присвоение должно сбрасывать накопленное прибавление (
add = 0), а прибавление не должно трогать присвоение. И вpushприсвоение применяется раньше прибавления. - Размер массивов
2n. Для рекурсивного дерева с нумерацией2*node,2*node + 1при , не равном степени двойки, нужно до узлов. - Тег на листе. Лист не вызывает
push, потому что в него никогда не заходим «частично». Тег на листе просто лежит и не мешает. Проверка «если лист — не проталкивать» не нужна, но и не вредит.
Когда ленивое дерево не нужно
Ленивое дерево — тяжёлый инструмент. Перед тем как его писать, проверьте, нет ли способа проще:
- Все изменения до всех запросов (сначала прибавления на отрезках, потом чтение) — достаточно разностного массива за .
- Прибавление на отрезке и запрос одного элемента — дерево Фенвика на разностях, код в пять строк.
- Прибавление на отрезке и сумма на отрезке — тоже Фенвик, но с двумя массивами. Получается короче ленивого дерева.
- Ограничения небольшие, , а операции сложные — sqrt-декомпозиция: медленнее, но проще отладить.
- Нужна вставка и удаление в середину массива — дерево отрезков не подходит, смотрите в сторону декартова дерева, где ленивые теги работают по тому же принципу.
Ленивое дерево незаменимо, когда операций изменения несколько видов, или когда запрос — минимум либо максимум (Фенвик с ними на отрезках не справляется).
Где встречается на собеседованиях
Ленивое дерево отрезков редко ждут на стандартном интервью уровня middle: его код длинный, и за 40 минут легко ошибиться. Но оно встречается в трёх ситуациях:
- Follow-up к задаче с отрезками. «А если операций изменения и они идут вперемешку с запросами?» Достаточно назвать структуру и объяснить, что хранится в узле и как работает
push. - Задачи LeetCode уровня Hard: Falling Squares (699), Range Module (715) с присвоением 0/1 на отрезке, My Calendar III (732) с прибавлением и максимумом, Handling Sum Queries After Update (2569) с инвертированием битов на отрезке.
- Олимпиадные секции и компании с сильным алгоритмическим фильтром, где дерево отрезков считается базовым инструментом.
На интервью хорошо работает такой порядок: сначала словами описать инвариант (значение узла верное, тег — долг детям), затем написать apply, push, pull и только потом общий каркас update/query. Если интервьюер видит, что вы понимаете роль каждой функции, мелкая опечатка в индексах прощается.
Что запомнить
- Тег в узле означает «уже учтено в значении узла, ещё не передано детям».
pushперед спуском (вupdateи вquery),pullпосле рекурсии вupdate.- Для суммы операции нужна длина отрезка, для минимума и максимума — нет.
- Присвоению нужен маркер «тега нет», отличный от любого допустимого значения.
- Несколько видов операций сворачиваются в один тег с фиксированным порядком применения: для присвоения и прибавления это
(set, add). - Любое ленивое дерево проверяйте стресс-тестом против наивного массива.