Интервальное дерево: другое поле - другая операция

Если ты понимаешь, что интервальное дерево - это BST по левому концу с полем «макс правый конец поддерева», и как это поле за O(log n) находит пересекающийся отрезок, отбрасывая поддерево, листай до «Теперь сам».

Как думаешь, как быстро найти пересекающийся отрезок

Задача: есть набор отрезков (брони переговорки по времени, диапазоны IP, интервалы генома), и спрашивают - пересекается ли данный отрезок [l, r] с каким-нибудь из набора? В лоб - перебрать все и проверить каждый: O(n) на запрос. Хочется O(log n). Отрезки можно сложить в дерево поиска по ЛЕВОМУ концу - но одного этого мало: два отрезка пересекаются по сложному условию (l ≤ чужой_верх И чужой_низ ≤ r), которое по левому концу напрямую не проверить. Нужна подсказка, позволяющая на каждом узле отбросить ЦЕЛОЕ поддерево, где пересечений точно нет. Такой подсказкой станет одно дополнительное число в узле - максимальный правый конец среди всех отрезков поддерева.

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

Диспетчер, раскладывающий заявки на аренду зала по времени начала, и на каждой стопке заявок пометка: «самое позднее ОКОНЧАНИЕ в этой стопке - такое-то». Пришёл клиент с интервалом - ищем конфликт. Смотрим левую стопку: если там самое позднее окончание РАНЬШЕ, чем начало клиента, значит все заявки слева заканчиваются до его прихода - конфликта там быть не может, стопку целиком откладываем. Иначе лезем в неё. Пометка «самое позднее окончание» позволяет отбрасывать стопки не глядя внутрь - и находить конфликт за считанные шаги, а не перебором всех заявок.

Механизм: BST по левому концу + поле max

Узел хранит отрезок [низ, верх]; КЛЮЧ дерева - левый конец низ. Дополнительное поле:

max(узел) = наибольший ВЕРХНИЙ конец среди всех отрезков поддерева
          = max(узел.верх, max(узел.лево), max(узел.право))     ← восстановимо из детей за O(1)

Запрос «найти отрезок, пересекающий [l, r]» (два отрезка пересекаются, если низ ≤ r И l ≤ верх):

поиск_пересечения(узел, l, r):
    пока узел не пуст:
        если отрезок узла пересекает [l, r]:  вернуть его
        если узел.лево не пусто И max(узел.лево) >= l:
            узел = узел.лево          # в левом поддереве МОЖЕТ быть пересечение
        иначе:
            узел = узел.право         # слева все верхние концы < l → пересечений нет, идём вправо
    вернуть «нет»

Разбор ключевого шага: если max(узел.лево) < l, то ВСЕ отрезки левого поддерева заканчиваются раньше l, значит ни один не дотянется до [l, r] - левое поддерево отбрасываем целиком и идём вправо. Так на каждом узле отсекается одна сторона, спуск идёт по одному пути - O(log n). Поле max обновляют при вставке/удалении на пути и при вращениях (O(1) по формуле) - балансировка цела, как и с полем size.

Правило

Интервальное дерево - тот же приём дополнения с ДРУГИМ полем: BST по левому концу отрезков плюс поле max (наибольший правый конец поддерева, восстановимо из детей за O(1)). Оно за O(log n) находит отрезок, ПЕРЕСЕКАЮЩИЙ данный: если max(левого поддерева) < начала запроса, все левые отрезки кончаются раньше - отбрасываем их и идём вправо, иначе влево. Поле обновляют при вставках/удалениях и вращениях (O(1)), балансировка не меняется. Сменил поле (size → max конца) - получил новую операцию (ранг → пересечение), не трогая старую структуру.

Разбор: почему поле max позволяет отбросить целое поддерево

Вся скорость держится на одном наблюдении. Два отрезка пересекаются, только если один начинается не позже, чем другой кончается. Стоя в узле, мы хотим понять: может ли в ЛЕВОМ поддереве быть отрезок, пересекающий [l, r]? Для пересечения такому отрезку нужно кончаться не раньше l (его верхний конец ≥ l). Поле max(левого) - это САМЫЙ ПОЗДНИЙ верхний конец во всём левом поддереве. Если даже он < l, то и все остальные там кончаются ещё раньше - НИ ОДИН не дотянется до l, пересечения в левом поддереве невозможны, и мы отбрасываем его целиком, не заглядывая. Одно число заменило проверку всех отрезков поддерева. А если max(левого) ≥ l, пересечение ТАМ возможно (не гарантировано, но возможно) - идём влево проверять. А почему тогда безопасно отбрасывать ПРАВОЕ поддерево, уходя влево? Потому что если в левом поддереве есть отрезок с концом ≥ l, но пересечения там всё же нет, то этот отрезок начинается ПОЗЖЕ r; а все отрезки правого поддерева начинаются не раньше него (дерево упорядочено по левому концу) - значит и они начинаются позже r, и пересечения справа тоже нет. В любом случае на каждом узле отсекается одна ветвь, и спуск - O(log n). Это и есть сила дополнения: удачно выбранное поле превращает «проверить всех» в «дойти».

Разбор: почему это тот же приём, что и порядковая статистика

Стоит увидеть, что интервальное дерево и дерево порядковой статистики - НЕ два разных изобретения, а один шаблон с разной начинкой. Шаблон: (1) берём сбалансированное BST; (2) добавляем в узел поле, восстановимое из детей за O(1); (3) поле обновляем при вставке/удалении и вращениях (O(1)); (4) новая операция спускается по дереву, используя поле, чтобы на каждом узле отбросить поддерево. Меняется лишь поле и правило спуска: size (число узлов) → операции про ПОЗИЦИЮ (select, rank); max правого конца → операция про ПЕРЕСЕЧЕНИЕ; сумма поддерева → диапазонные суммы; min/max ключа → быстрые экстремумы поддерева. Старые операции (поиск, вставка, удаление, баланс) при этом не меняются вовсе - дополнение их не касается. Поэтому дополнение - это не набор трюков, а один метод: «какое локальное поле ответит на мой запрос спуском?». Освоив шаблон, ты конструируешь нужную структуру под задачу, а не ищешь готовую.

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

Первая ошибка - выбрать поле, не отвечающее на нужный вопрос: для пересечения интервалов нужен именно МАКСИМУМ правого конца (не левого, не сумма) - только он позволяет отбросить поддерево «все кончаются раньше l». Поле подбирают ПОД правило отсечения. Вторая - забыть обновлять max при вращениях: после балансировки поле у переставленных узлов станет неверным, и запрос начнёт пропускать пересечения. Третья - неверное условие пересечения: отрезки [a,b] и [l,r] пересекаются, если a ≤ r И l ≤ b; перепутаешь знаки - получишь ложные ответы. Четвёртая - ждать, что интервальное дерево вернёт ВСЕ пересечения за O(log n): за O(log n) оно находит ОДНО (или отвечает «есть/нет»); чтобы перечислить все k пересечений, нужно O(k·log n) или O(k + log n) в зависимости от реализации.

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

Интервальные деревья решают запросы про диапазоны там, где перебор O(n) недопустим: расписания и брони (конфликтует ли новая встреча с существующими), сети (какие правила файрвола накрывают данный порт/IP-диапазон), вычислительная геометрия (пересечения отрезков, оконные запросы), биоинформатика (перекрытия участков генома), базы данных с типами-диапазонами. Но главная ценность урока - не конкретная структура, а ЗАКРЕПЛЕНИЕ приёма дополнения: ты увидел его дважды (size для рангов, max для пересечений) и теперь понимаешь шаблон, а не два частных случая. Это меняет способ мышления: встретив запрос, которого «стандартная структура не умеет», ты спрашиваешь «каким полем дополнить дерево, чтобы ответить спуском?» - и часто конструируешь решение сам. Тот же метод даёт диапазонные суммы (следующая глава - дерево отрезков и Фенвика довели идею до предела). Дополнение - один из самых практичных инструментов в арсенале, и он именно про КОНСТРУИРОВАНИЕ структур под задачу.

Теперь сам

В интервальном дереве (см. схему) запрос [13, 14] - есть ли пересекающийся отрезок? Пройди поиск и объясни, где поле max позволяет (или не позволяет) отбросить поддерево.