Дерево отрезков: диапазонный запрос за логарифм

Если ты понимаешь, что дерево отрезков хранит свёртку диапазона в каждом узле, что запрос [l,r] собирается из O(log n) узлов, а обновление чинит O(log n) узлов на пути к корню, листай до «Теперь сам».

Как думаешь, как быстро считать сумму на отрезке И менять элементы

Сумму на отрезке [l, r] можно считать за O(1), если заранее насчитать ПРЕФИКСНЫЕ суммы (сумма[l..r] = pre[r] − pre[l−1]). Но у этого приёма роковой недостаток: если изменить ОДИН элемент, все префиксные суммы после него сломаются - пересчёт O(n). То есть префиксные суммы хороши для СТАТИЧЕСКОГО массива, но не для меняющегося. А если и запросы по диапазону, и изменения происходят постоянно (счётчики, агрегаты в реальном времени)? Наивно каждый запрос - O(n) (пройти отрезок), обновление - O(1); или наоборот. Хочется, чтобы ОБА были дёшевы. Ключ - не хранить суммы «плоско», а разложить массив на ИЕРАРХИЮ отрезков, где изменение задевает лишь немногие уровни, а запрос собирается из немногих готовых кусков.

На что это похоже

Оргструктура компании с суммами по подразделениям. Внизу - сотрудники (элементы), выше - отделы, управления, дирекции; в каждом узле висит СУММАРНЫЙ бюджет его подразделения. Хочешь узнать бюджет по нескольким отделам (диапазон) - не складываешь всех сотрудников поштучно, а берёшь уже готовые суммы подходящих подразделений: пара управлений плюс один отдел - и готово. Изменил зарплату одного сотрудника - правишь суммы только по цепочке его начальников вверх до гендиректора, а не всю компанию. Дерево отрезков - такая иерархия сумм: запрос собирается из готовых узлов, правка идёт по одной ветке вверх.

Механизм: дерево свёрток и две операции

Массив кладём в ЛИСТЬЯ дерева. Каждый внутренний узел покрывает отрезок и хранит его свёртку - пусть СУММУ (можно min, max, gcd - любую ассоциативную операцию):

узел покрывает [lo, hi]:
    если lo == hi:  это лист, хранит a[lo]
    иначе:          mid = (lo+hi)//2
                    левый ребёнок покрывает [lo, mid], правый [mid+1, hi]
                    сумма узла = сумма левого + сумма правого

Запрос суммы [l, r] - спускаемся от корня, комбинируя узлы:

запрос(узел [lo,hi], l, r):
    если [lo,hi] ВНЕ [l,r]:            вернуть 0            (не пересекается)
    если [lo,hi] ЦЕЛИКОМ внутри [l,r]: вернуть сумму узла   (готовый кусок!)
    иначе:  вернуть запрос(лево) + запрос(право)           (частично - делимся)

Запрос [l, r] разбивается на O(log n) узлов, целиком лежащих внутри диапазона, - их суммы уже готовы, складываем.

Обновление элемента a[i] = x - меняем лист и чиним суммы по пути к корню:

обновить(i, x):  поставить x в лист i, затем пересчитать сумму у каждого предка до корня

На пути от листа к корню ровно O(log n) узлов - столько и правим. Итог: и запрос, и обновление - O(log n).

Правило

Дерево отрезков отвечает на диапазонный запрос (сумма/min/max на [l, r]) и меняет элемент - ОБА за O(log n). Листья - элементы массива, каждый внутренний узел хранит СВЁРТКУ своего отрезка. Запрос [l, r] собирается из O(log n) узлов, целиком лежащих внутри диапазона (их свёртки готовы); обновление элемента чинит свёртки O(log n) узлов на пути от листа к корню. Так решается то, что не могут ни наивный проход (O(n) на запрос), ни префиксные суммы (O(n) на обновление): и запросы, и изменения дёшевы одновременно.

Разбор: почему запрос разбивается ровно на O(log n) узлов

Кажется, произвольный отрезок [l, r] может задеть много узлов - но их всегда O(log n), и вот почему. Спускаясь, на каждом узле мы в одном из трёх состояний: узел ВНЕ запроса (отбрасываем, 0), узел ЦЕЛИКОМ внутри (берём готовую свёртку, вглубь не идём), узел ЧАСТИЧНО пересекает (делимся на двух детей). «Целиком внутри» и «вне» - тупики, дальше не спускаемся. Спускаемся только через ЧАСТИЧНЫЕ узлы, а их на каждом уровне не больше ДВУХ - один у левой границы l, один у правой r (внутри между ними всё либо целиком внутри, либо целиком вне). Значит на каждом из log n уровней добавляется не больше пары «пограничных» узлов - итого O(log n) узлов в разбиении запроса. Это как два спуска (к l и к r), между которыми всё берётся готовыми блоками. Отсюда O(log n) на запрос вместо O(n).

Разбор: почему дерево отрезков бьёт префиксные суммы при обновлениях

Сравним честно. Префиксные суммы: запрос [l,r] - O(1) (вычитание), НО обновление одного элемента - O(n) (все префиксы после него сдвигаются). Дерево отрезков: запрос - O(log n), обновление - тоже O(log n). Для СТАТИЧЕСКОГО массива (только запросы) префиксные суммы лучше - O(1) против O(log n). Но как только появляются ОБНОВЛЕНИЯ вперемешку с запросами, префиксные суммы разваливаются: каждое изменение - линейный пересчёт. Дерево отрезков платит логарифм за ОБЕ операции, зато обе быстры ВСЕГДА. Причина - иерархия: изменение одного элемента задевает лишь узлы НА ПУТИ к корню (по одному на уровень, O(log n)), а не все суммы, потому что каждый элемент входит лишь в log n вложенных отрезков. Это фундаментальный размен: плоская структура (префиксы) даёт O(1) запрос ценой дорогого обновления; иерархическая (дерево) уравнивает обе операции в O(log n). Выбор - как всегда, по профилю нагрузки: чисто чтения → префиксы; чтения вперемешку с записями → дерево отрезков.

Что ломается без этого

Первая ошибка - применять префиксные суммы там, где элементы МЕНЯЮТСЯ: каждое обновление станет O(n), и на потоке изменений всё встанет; для динамики нужно дерево отрезков (или Фенвика - следующий урок). Вторая - в запросе спускаться в узлы, ЦЕЛИКОМ лежащие внутри [l, r]: их свёртка уже готова, углубляться не надо - иначе потеряешь O(log n) и получишь O(n). Три случая (вне / целиком внутри / частично) обязательны. Третья - забыть починить свёртки ВВЕРХ после обновления листа: поправишь лист, но суммы предков останутся старыми, и запросы соврут. Обновление всегда идёт до корня. Четвёртая - думать, что дерево отрезков только для сумм: подойдёт любая АССОЦИАТИВНАЯ свёртка (min, max, gcd, произведение) - меняется лишь операция объединения детей.

Зачем это в работе

Дерево отрезков - рабочая лошадка задач с диапазонными запросами по МЕНЯЮЩИМСЯ данным: агрегаты в реальном времени (сумма/макс продаж за период при постоянных обновлениях), геометрия (сканирующая прямая, пересечения), обработка сигналов, движки таблиц и электронных таблиц, олимпиадные задачи про диапазоны. Оно ценно тем, что снимает ложную дилемму «либо быстрый запрос, либо быстрое обновление»: даёт O(log n) на оба. Понимать его - значит уметь отвечать на «сумма/мин/макс на отрезке, и данные меняются» без деградации, а также видеть общий приём: разложить массив в иерархию свёрток, где каждый элемент влияет лишь на log n узлов. Это прямое развитие идеи дополнения из прошлой главы (узел хранит свёртку поддерева), доведённое до полноценной структуры диапазонных запросов. Следующий урок - дерево Фенвика: то же для сумм, но компактнее и проще; а дальше - как деревом отрезков обновлять сразу ЦЕЛЫЙ диапазон (отложенные обновления).

Теперь сам

В дереве отрезков над массивом [3, 4, 6, 5] (см. схему) спрашивают сумму на [1, 3]. Из каких узлов соберётся ответ и сколько их - и почему не три (по числу элементов в диапазоне)?