Дерево отрезков

С 1 января 1941 года по 31 декабря 2025-го прошёл 31 046 дней. Какой из них был самым холодным зимой 1968/69 года? Сколько дождя выпало за 2010-е? Когда было жарче всего летом 2025-го? Префиксные суммы ответят про дождь одним вычитанием, но про минимум не ответят, а если ряд поправят, их придётся пересчитывать целиком. Дерево отрезков заранее знает ответ для 62 091 куска ряда — от всех 85 лет до одного дня — и любой период собирает из нескольких таких кусков. Ниже это дерево целиком: строка — уровень, прямоугольник — узел, цвет — средняя температура его дней.

Зима 1968/69 года — 90 дней — складывается из 8 узлов, а чтобы их найти, дерево заглядывает в 43. Все 85 лет — это один узел, корень. Посмотрите на строки дерева сверху вниз. Наверху цвета почти одинаковые: средняя за десятилетия меняется на градус-другой. Узлы в несколько месяцев ложатся полосами — лето, зима, лето, — а внизу, где узел — несколько дней, видна погода. Каждый уровень — тот же ряд, только в своём масштабе.

Теперь поменяйте данные. Выберите «Прибавить», поставьте −1 °C и нажмите «1941–1950». Все 3652 дня десятилетия сдвинутся, а поправка посетит 23 узла и оставит записки на пяти. Самым жарким днём 85 лет был 9 августа 1944 года, 31,4 °C; после поправки им станет 14 июля 2023 года, 31,3 °C. Треугольники — записки: поправка дошла до этих узлов и дальше не пошла. Узлы под ними приглушены: они ещё не знают, что их дни стали холоднее.

Идея

Делим массив пополам, каждую половину — снова пополам, и так до отдельных элементов. Каждый кусок — узел дерева, и в нём записан ответ для этого куска: сумма, минимум, максимум. Любой отрезок массива складывается не больше чем из двух узлов на каждом уровне, поэтому запрос — O(log n). Изменение элемента меняет ответы только у его предков — тоже O(log n). А поправку к целому отрезку узел, который лежит в отрезке целиком, учитывает в своём ответе сразу, а детям оставляет записку — до тех пор, пока кому-нибудь не понадобится спуститься ниже.

Префиксные суммы хранят n ответов «от начала до i» и вычитают два из них. Это работает, потому что у сложения есть обратное действие. У минимума его нет: зная минимум января–марта и минимум января–февраля, минимум марта не узнаешь. Дерево обходится без вычитания: оно хранит ответы для кусков, которые не пересекаются, и только склеивает их. Склейка должна быть ассоциативной: сумма, минимум, максимум, наибольший общий делитель, произведение матриц. Если узлу хватает того, что знают дети, дерево работает.

Узел номер v отвечает за полуинтервал [lo, hi), его дети — узлы 2v и 2v + 1 с половинами [lo, mid) и [mid, hi), где mid = ⌊(lo + hi)/2⌋. Нумерация та же, что у двоичной кучи, только корень — номер 1. Узлов 2n − 1: листьев n, внутренних на один меньше. Для 31 046 дней получается 62 091 узел и 16 уровней.

Из каких узлов складывается отрезок

Запрос спускается от корня. Узел, который не пересекается с отрезком, отвечает «ничего»: ноль для суммы, плюс бесконечность для минимума. Узел, который лежит в отрезке целиком, отдаёт свой готовый ответ, и вниз запрос не идёт. Остаются узлы, которые задеты частично: только у них запрос спрашивает обоих детей и склеивает их ответы.

В сцене это видно на любом периоде: оранжевые узлы идут лесенкой — с каждого края по одному на уровень, крупные посередине, мелкие у краёв. Длина отрезка на число шагов почти не влияет. Летние 92 дня 2025 года собираются из трёх узлов, все 3652 дня 2010-х — из одиннадцати, а посещений в обоих случаях — 31 и 47 при пределе 64.

Поправка к целому отрезку

Изменить один день просто: поменять лист и пересчитать его предков, один путь до корня. Иначе с поправкой к отрезку. Климатологи гомогенизируют ряды наблюдений: когда метеостанцию переносят или меняют прибор, в ряду появляется скачок, не связанный с погодой, и показания за целый период сдвигают на оценку этого скачка. Поправить десять лет по одному дню — 3652 пути до корня. Но большинству узлов под поправкой знать о ней прямо сейчас незачем: их никто не спрашивает.

Поправка спускается по дереву как запрос. Узел, который лежит в отрезке целиком, исправляет свой ответ сразу — прибавить d к минимуму и максимуму, d·(hi − lo) к сумме — и записывает для детей записку «+d», а вниз не идёт. Когда позже кто-нибудь спускается через этот узел — запрос, поправка или поиск, — узел сначала отдаёт записку детям. Это отложенные операции, или ленивое проталкивание: работы ровно столько же, сколько у запроса, O(log n).

Ниже то же дерево на 16 днях января и февраля 1969 года, в целых градусах. В узле — минимум его дней. Выберите дни, действие и нажмите «Выполнить»: дерево пройдёт шаг за шагом и подпишет, что делает.

Прибавьте +5 к дням 4–13: поправка ляжет на четыре узла — два крупных посередине получат записки, а дни 4 и 13 у краёв просто получат новые значения. Потом спросите минимум дней 6–9. Запрос пройдёт через узлы с записками и по дороге отдаст их детям; узлы в стороне от его пути так и останутся с записками. А потом снимите галочку «проталкивать записки» и повторите: прибавьте, спросите — и дерево ответит неверно.

Записок бывает две: «прибавить d» и «присвоить x». Если на узле уже висит одна, а приходит вторая, их нужно склеить в одну, и порядок важен. «Присвоить x, потом прибавить d» — это «присвоить x + d». «Прибавить d, потом присвоить x» — это просто «присвоить x»: прибавка стирается. Почему вообще всё сходится, объясняет одно утверждение.

Спуск: первый день ниже нуля

Дерево умеет не только отвечать «сколько», но и искать «где». Пусть нужен первый день после 1 августа со среднесуточной температурой не выше нуля. Перебирать дни подряд долго, если осень тёплая. Дерево идёт сверху: если минимум узла выше нуля, такого дня в нём нет, и узел пропускается целиком; иначе нужный день внутри, и спуск идёт в левого ребёнка, а если там не нашлось — в правого. Неудачные спуски бывают только вдоль левой границы поиска, удачный — один путь до листа, поэтому весь поиск — O(log n).

Для 85 осеней такой спуск в среднем посещает 25 узлов. Раньше всех такой день наступил в 2021 году — 6 октября, позже всех в 2023-м — 8 декабря. Тем же спуском сцена и листинг находят дату минимума: сначала запрос узнаёт, чему равен минимум, потом спуск ищет первый день, где он достигается. Поиск по дереву сумм работает так же — «первый i, где сумма от начала превышает s», — и так устроена выборка с вероятностями, пропорциональными весам: случайное s от нуля до общей суммы и один спуск.

Код

Рекурсивное дерево с суммой, минимумом и максимумом, две записки и спуск. Демо — на всём ряду погоды: те же периоды, что в сцене, поправка к 1940-м, «а если бы в мае 1985 года не было дождей» и первые нулевые дни осеней. Счётчики узлов совпадают со сценой.

winter 1968/69: 90 days, mean -7.7, min -19.1 on 1969-01-27, max 2.9 on 1968-12-03, rain 99.8 mm
  the answer is made of 8 node(s), 43 visited; a loop would read 90 days

Присвоение нуля всему маю 1985 года посетило 37 узлов. Годовая сумма осадков упала с 776,3 до 621,9 мм, а самым дождливым днём 85 лет вместо 24 мая 1985 года, 53,2 мм, стало 22 июля 1953 года, 52,3 мм.

Если отрезки менять не нужно — только отдельные элементы, — дерево пишут без рекурсии. Листья кладут в ячейки n…2n − 1, родитель ячейки i — ячейка i/2, а запрос поднимается от двух концов отрезка одновременно: если конец — правый ребёнок (для левого конца) или левый (для правого), его узел целиком внутри, и его ответ берётся. Массив — ровно 2n ячеек при любом n, не только при степени двойки; этот вариант стал известен по записи Al.Cash «Efficient and easy segment trees» на Codeforces. В листинге узлы хранят не дождь, а номер дня, поэтому дерево отвечает и «сколько», и «когда».

Сколько это стоит

Память — O(n). Рекурсивному дереву с делением пополам при n, не равном степени двойки, номера узлов доходят почти до 4n, поэтому массивы берут с этим запасом; дереву снизу вверх хватает 2n. Каждая записка — ещё одно число на узел.

Сравним три способа на смеси: половина операций меняет один элемент, половина спрашивает сумму случайного отрезка. Просмотр меняет элемент даром, но сумму считает проходом. Префиксные суммы отвечают одним вычитанием, но после каждого изменения пересчитывают суммы от этого места до конца. Дерево снизу вверх делает и то и другое за путь длиной log n.

Дерево почти не замечает роста: от тысячи до миллиона элементов время на Go растёт чуть больше чем втрое, на Python — в два с половиной раза. На миллионе элементов дерево обгоняет просмотр в 260 раз на Go и в 110 раз на Python, а префиксные суммы — в тысячи раз: пересчёт хвоста после каждого изменения оказывается самой дорогой частью. На тысяче элементов в Python просмотр почти не уступает дереву: сумма среза считается на C, а дерево платит интерпретатору за каждый шаг. Если данные маленькие или почти не меняются, дерево не нужно.

Родственники и выбор

• Данные не меняются, нужна сумма — префиксные суммы: O(1) на запрос.
• Данные не меняются, нужен минимум или максимум — разреженная таблица: O(1) на запрос после O(n log n) подготовки.
• Суммы с изменениями элементов — дерево Фенвика: те же O(log n), вдвое меньше памяти и цикл в три строки. Но минимум и поправки к отрезку с присвоением ему не по силам.
• Склейку трудно сделать ассоциативной — корневая декомпозиция: блоки по √n и O(√n) на операцию.
• Нужны старые версии массива — персистентное дерево отрезков: каждое изменение копирует только свой путь.

В узле не обязательно лежит число. Если хранить в узле четыре числа — сумму, лучший префикс, лучший суффикс и лучший подотрезок, — дерево отвечает, какой участок ряда дал наибольшую сумму, и это тоже склеивается из двух детей. Если значения — координаты, дерево по ним строят после сжатия координат. А дерево отрезков над путями дерева — тяжёло-лёгкая декомпозиция — отвечает на запросы о путях в дереве.

Где работает

Обучение с подкреплением. В 2015 году Том Шауль и соавторы из Google DeepMind предложили учить агента чаще на тех случаях из прошлого опыта, где он ошибся сильнее, — выборка с вероятностями, пропорциональными приоритетам. Для этого в статье описано «дерево сумм»: в листьях приоритеты, в каждом узле — сумма детей, а выборка — спуск по случайному числу от нуля до суммы в корне. В библиотеке OpenAI Baselines для этого есть классы SumSegmentTree и MinSegmentTree.

Геометрия. Площадь объединения прямоугольников считают заметающей прямой: прямая идёт слева направо, и дерево отрезков над координатами по вертикали помнит, какая часть прямой сейчас накрыта.

Олимпиады. Одна из главных структур олимпиадного программирования: запросы на отрезке, изменения, спуск, отложенные операции, деревья на путях графа.

История

В 1977 году Виктор Кли спросил, можно ли найти длину объединения n отрезков на прямой быстрее, чем за O(n log n). В том же году Джон Бентли в неопубликованных заметках разобрал двумерный вариант — площадь объединения n прямоугольников — и решил его за O(n log n) заметающей прямой, а отрезки, которые прямая пересекает, держал в структуре, которую теперь называют деревом отрезков. Вопрос о трёх и более измерениях под названием «задача Кли о мере» до сих пор не закрыт до конца.

У названия двойная жизнь. В учебниках вычислительной геометрии деревом отрезков называют структуру, которая хранит сами отрезки и отвечает, какие из них накрывают данную точку. В олимпиадном программировании так называют дерево, которое отвечает на запросы о сумме и минимуме на отрезке массива, — то, о чём эта статья. Устроены оба одинаково, делением пополам, а хранят разное.

Задачи

В первой задаче поправки к ряду погоды и запросы о самом холодном и самом тёплом дне перемешаны: нужна прибавка к отрезку с записками. Во второй отрезки ряда заменяются целиком, а спрашивают первый день, холоднее заданного, — присвоение и спуск в одном дереве. Тесты обеих — настоящая погода Алматы.