Дерево интервалов: как быстро находить пересекающиеся отрезки
Дерево интервалов простыми словами: дерево поиска с полем max_hi, поиск любого и всех пересечений, центрированное дерево для точек, My Calendar I и II на Python и сравнение с деревом отрезков.
Коротко
| Что | Суть |
|---|---|
| Задача | Хранить набор интервалов и быстро находить те, что пересекаются с запросом |
| Главная идея | Дерево поиска по началам интервалов, в каждой вершине — максимум концов в её поддереве |
| Сложность | Вставка и удаление , «есть ли пересечение» , все штук — |
| Центрированный вариант | Статичный набор, запрос «какие интервалы содержат точку» за |
| Где спрашивают | My Calendar I/II/III, Range Module, планировщики, базы геоданных, отладчики памяти |
- Дерево интервалов — это не новая структура с нуля, а дополненное дерево поиска: к обычному сбалансированному дереву добавляется одно поле.
- Если интервалы в наборе не пересекаются друг с другом, дерево интервалов не нужно: хватит отсортированного списка и бинпоиска.
Какую задачу решаем
У нас есть меняющийся набор интервалов: брони переговорок, выделенные участки памяти, временные окна задач. Приходят запросы двух видов:
- Добавить или удалить интервал.
- Найти интервалы, которые пересекаются с отрезком , — любой один или все.
Везде ниже интервалы полуоткрытые: , начало входит, конец нет. Так встреча с 10 до 20 и встреча с 20 до 30 не конфликтуют. Два полуинтервала пересекаются тогда и только тогда, когда
Это условие стоит выучить наизусть: в нём нет ни одного «или», и его легко проверить на случаях «один внутри другого», «касаются концами» и «один левее другого».
Наивные решения
Список и перебор. Храним интервалы в списке, на запрос проверяем все. Вставка , запрос . При операций — проверок, слишком медленно.
Сортировка по началу. Если отсортировать интервалы по lo, бинпоиском можно отрезать все интервалы с : они точно правее. Но с другой стороны отсечь нечего. Интервал, начавшийся очень давно, может тянуться до сих пор, и чтобы его найти, придётся просмотреть всё, что левее. Худший случай — снова .
Именно эта асимметрия и подсказывает решение: по началам мы умеем отсекать, а про концы нам нужна сводка — «есть ли где-то в этой части набора интервал, который заканчивается достаточно поздно».
Идея: дерево поиска плюс максимум концов
Возьмём двоичное дерево поиска с ключом lo (при равных началах — пара (lo, hi)). В каждой вершине, кроме самого интервала, храним
то есть самый поздний конец среди всех интервалов поддерева.
Это поле даёт ровно то отсечение, которого не хватало:
- если , все интервалы поддерева заканчиваются до начала запроса — туда не идём;
- если , то и сама вершина, и всё её правое поддерево (там начала ещё больше) начинаются после конца запроса — правое поддерево не нужно.
Поле max_hi пересчитывается локально, из самой вершины и двух детей. Поэтому его легко поддерживать при любых изменениях дерева: после вставки, удаления или поворота достаточно пересчитать его у изменившихся вершин снизу вверх. Это общее свойство дополненных деревьев, на нём же держатся размеры поддеревьев в порядковой статистике.
Почему нужна балансировка
Все оценки верны только для сбалансированного дерева. Если вставлять интервалы в порядке возрастания начал — а брони в календаре часто так и приходят, — обычное BST выродится в список, и всё снова станет .
В учебнике Кормена дерево интервалов строят на красно-чёрном дереве. Для собеседования и для Python удобнее декартово дерево: балансировка случайными приоритетами, всего две операции split и merge, а пересчёт max_hi ставится в одно место — функцию pull.
Реализация на декартовом дереве
import random class Node: __slots__ = ('lo', 'hi', 'max_hi', 'prio', 'left', 'right') def __init__(self, lo: int, hi: int): self.lo, self.hi = lo, hi # интервал [lo, hi) self.max_hi = hi # максимум hi во всём поддереве self.prio = random.random() # приоритет декартова дерева self.left = self.right = None def max_hi(node) -> float: return node.max_hi if node else float('-inf') def pull(node: Node) -> Node: """Пересчитывает дополнительное поле после любого изменения детей.""" node.max_hi = max(node.hi, max_hi(node.left), max_hi(node.right)) return node def split(node, key): """Делит дерево на (ключи < key, ключи >= key). Ключ — пара (lo, hi).""" if node is None: return None, None if (node.lo, node.hi) < key: node.right, r = split(node.right, key) return pull(node), r l, node.left = split(node.left, key) return l, pull(node) def merge(a, b): """Склеивает деревья, где все ключи a меньше всех ключей b.""" if a is None or b is None: return a or b if a.prio > b.prio: a.right = merge(a.right, b) return pull(a) b.left = merge(a, b.left) return pull(b)
Единственное отличие от обычного декартова дерева — вызовы pull в каждом месте, где у вершины поменялись дети. Пропустите хотя бы один — и max_hi где-то станет устаревшим, а поиск начнёт молча терять интервалы.
Теперь сама структура:
class IntervalTree: def __init__(self): self.root = None def insert(self, lo: int, hi: int) -> None: l, r = split(self.root, (lo, hi)) self.root = merge(merge(l, Node(lo, hi)), r) def remove(self, lo: int, hi: int) -> None: l, r = split(self.root, (lo, hi)) mid, r = split(r, (lo, hi + 1)) # mid — все копии [lo, hi) if mid: mid = merge(mid.left, mid.right) # удаляем одну копию self.root = merge(merge(l, mid), r) def any_overlap(self, lo: int, hi: int): """Любой интервал, пересекающийся с [lo, hi), или None. O(log n).""" node = self.root while node: if node.lo < hi and lo < node.hi: return node.lo, node.hi if node.left and node.left.max_hi > lo: node = node.left else: node = node.right return None def all_overlaps(self, lo: int, hi: int) -> list[tuple[int, int]]: """Все интервалы, пересекающиеся с [lo, hi).""" out = [] def go(node): if node is None or node.max_hi <= lo: return # все концы поддерева левее запроса go(node.left) if node.lo < hi and lo < node.hi: out.append((node.lo, node.hi)) if node.lo < hi: # правее только интервалы с lo >= node.lo go(node.right) go(self.root) return out
Проверим на примере:
tree = IntervalTree() for lo, hi in [(15, 20), (10, 30), (17, 19), (5, 20), (12, 15), (30, 40)]: tree.insert(lo, hi) print(tree.all_overlaps(14, 16)) # [(5, 20), (10, 30), (12, 15), (15, 20)] print(tree.any_overlap(21, 23)) # (10, 30) print(tree.any_overlap(40, 50)) # None tree.remove(10, 30) print(tree.any_overlap(21, 23)) # None
Запрос [14, 16) не задел (17, 19) — он начинается после конца запроса, и (30, 40) — тоже. А (12, 15) попал: точка 14 лежит внутри. Код я дополнительно прогнал на сотнях случайных последовательностей вставок, удалений и запросов против перебора.
all_overlaps возвращает интервалы в порядке ключей, то есть отсортированными по началу. Это бесплатный бонус обхода в глубину слева направо.
Почему поиск одного пересечения корректен
Самое тонкое место — any_overlap. Он спускается по одному пути и ни разу не возвращается. Почему, свернув влево, мы не можем пропустить ответ, лежащий справа?
Пусть мы в вершине v, она сама запрос не пересекает, и v.left.max_hi > lo. Мы идём влево. Рассмотрим два случая.
- В левом поддереве есть пересечение — отлично, найдём его там.
- В левом поддереве пересечений нет. Но там есть интервал
w, у которогоw.hi = v.left.max_hi > lo. Раз он не пересекает запрос, а конец у него правееlo, значит, он целиком правее:w.lo >= hi. Все интервалы правого поддерева начинаются не раньшеw.lo— они тоже правее запроса. Значит, пересечения нет нигде, и ответNoneверен.
А если v.left.max_hi <= lo, левое поддерево целиком заканчивается до запроса, и идти туда бессмысленно. Так на каждом шаге отбрасывается одна из половин, и поиск занимает , то есть для сбалансированного дерева.
Сложность
| Операция | Время | Комментарий |
|---|---|---|
| Вставка, удаление | ожидаемо, для декартова дерева | |
| Есть ли пересечение | один путь от корня | |
| Все пересечения | — размер ответа | |
| Память | одно дополнительное число на вершину |
Оценка для всех пересечений получается так: каждый найденный интервал «оплачивает» не больше одного пути длины к себе, а поддеревья без ответов отсекаются сразу на входе. Поиск всех пересечений можно ускорить до на других структурах, но для дерева с одним полем max_hi это честная граница.
Центрированное дерево интервалов
Есть второй классический вариант, который в литературе тоже называют деревом интервалов. Он работает для статичного набора и отвечает на вопрос «какие интервалы содержат точку » — так называемый stabbing query.
Построение рекурсивное:
- Выбираем центр — медиану начал интервалов.
- Делим интервалы на три группы: целиком левее , целиком правее и те, что содержат .
- Интервалы, содержащие центр, храним в вершине в двух списках: по возрастанию начала и по убыванию конца.
- Левую и правую группы обрабатываем рекурсивно.
Хитрость в запросе. Пусть . Все интервалы в вершине содержат , значит, их концы правее — проверять нужно только начало. Идём по списку, отсортированному по началу, и останавливаемся на первом, который начинается правее : дальше начала только больше. Симметрично для идём по списку концов.
class CenteredNode: def __init__(self, intervals: list[tuple[int, int]]): # медиана начал: интервал с lo == center точно попадёт в here starts = sorted(lo for lo, _ in intervals) self.center = starts[len(starts) // 2] c = self.center here = [iv for iv in intervals if iv[0] <= c < iv[1]] left = [iv for iv in intervals if iv[1] <= c] right = [iv for iv in intervals if iv[0] > c] self.by_lo = sorted(here) # по возрастанию начала self.by_hi = sorted(here, key=lambda iv: -iv[1]) # по убыванию конца self.left = CenteredNode(left) if left else None self.right = CenteredNode(right) if right else None def stab(node: CenteredNode | None, x: int) -> list[tuple[int, int]]: """Все интервалы [lo, hi), содержащие точку x. O(log n + k).""" out = [] while node: if x < node.center: for lo, hi in node.by_lo: # все hi > center > x, проверяем только lo if lo > x: break out.append((lo, hi)) node = node.left else: for lo, hi in node.by_hi: # все lo <= center <= x, проверяем только hi if hi <= x: break out.append((lo, hi)) node = node.right return out intervals = [(1, 5), (2, 8), (6, 9), (7, 12), (10, 11), (3, 4)] root = CenteredNode(intervals) print(root.center) # 6 print(sorted(stab(root, 7))) # [(2, 8), (6, 9), (7, 12)] print(sorted(stab(root, 3))) # [(1, 5), (2, 8), (3, 4)] print(stab(root, 12)) # []
Деталь, на которой я сам споткнулся в первой версии: центр берётся из начал, а не из всех концов подряд. Если взять медиану всех точек, центр может совпасть с концом интервала, например для (3, 4). Тогда этот интервал по правилу полуоткрытости «целиком левее», уходит в левую группу, там центр снова выпадает на 4 — и рекурсия бесконечна. Медиана начал гарантирует, что хотя бы один интервал останется в вершине, а каждая из боковых групп содержит не больше половины интервалов. Отсюда глубина .
Каждая вершина на пути запроса тратит на неудачную проверку плюс на каждый найденный интервал, поэтому запрос — . Построение — , если сортировать один раз и аккуратно раздавать уже отсортированные списки детям; в коде выше для простоты сортировка повторяется на каждом уровне, это .
Минус центрированного дерева — вставлять и удалять интервалы в нём неудобно. Поэтому для динамических задач берут дополненное дерево поиска, а центрированное — для заранее известного набора, например при подготовке геометрических данных.
Задача: My Calendar I
LeetCode 729. Нужно реализовать календарь: метод book(start, end) добавляет бронь и возвращает True, если она ни с чем не пересекается, иначе возвращает False и ничего не добавляет.
С деревом интервалов это три строки:
class MyCalendar: def __init__(self): self.tree = IntervalTree() def book(self, start: int, end: int) -> bool: if self.tree.any_overlap(start, end): return False self.tree.insert(start, end) return True cal = MyCalendar() print([cal.book(s, e) for s, e in [(10, 20), (15, 25), (20, 30)]]) # [True, False, True]
Но здесь стоит остановиться. В My Calendar I все хранимые брони не пересекаются друг с другом — пересекающуюся мы бы не добавили. А у непересекающихся интервалов порядок по началам совпадает с порядком по концам. Значит, новой брони достаточно сравниться с двумя соседями: ближайшим слева и ближайшим справа. Это делается бинарным поиском по отсортированному списку начал, без всякого max_hi. На собеседовании хорошо сказать об этом вслух: дерево интервалов нужно, когда интервалы в наборе могут перекрываться.
Задача: My Calendar II
LeetCode 731. Теперь двойные брони разрешены, запрещены тройные. Вот тут интервалы в наборе перекрываются, и дерево интервалов становится полезным.
Держим два дерева: все брони и участки, где уже есть двойное пересечение. Новая бронь недопустима, если задевает хотя бы один двойной участок. Иначе находим все брони, которые она пересекает, и их общие части добавляем в дерево двойных.
class MyCalendarTwo: """Разрешены двойные брони, тройные — нет.""" def __init__(self): self.booked = IntervalTree() # все брони self.doubled = IntervalTree() # участки двойного пересечения def book(self, start: int, end: int) -> bool: if self.doubled.any_overlap(start, end): return False for lo, hi in self.booked.all_overlaps(start, end): self.doubled.insert(max(lo, start), min(hi, end)) self.booked.insert(start, end) return True cal2 = MyCalendarTwo() bookings = [(10, 20), (50, 60), (10, 40), (5, 15), (5, 10), (25, 55)] print([cal2.book(s, e) for s, e in bookings]) # [True, True, True, False, True, True]
Пересечение двух полуинтервалов — это [max(lo), min(hi)), и раз они пересекаются, оно непустое. Обратите внимание: тут нужен именно all_overlaps, одного найденного интервала недостаточно.
Для My Calendar III (максимальная кратность пересечений) удобнее дерево отрезков с отложенными операциями или подсчёт событий заметающей прямой: там нужны не сами интервалы, а число слоёв в каждой точке.
Дерево интервалов или дерево отрезков
Названия похожи, и на собеседовании их иногда путают. Разница принципиальная.
| Вопрос | Дерево интервалов | Дерево отрезков |
|---|---|---|
| Что хранит | Сами интервалы, по одному в вершине | Агрегат (сумма, максимум) над ячейками массива |
| Что возвращает | Конкретные пересекающиеся интервалы | Число: сумму, максимум, покрытие на отрезке |
| Координаты | Любые, хоть вещественные | Индексы массива, большие — через сжатие координат |
| Изменение набора | Вставка и удаление за | Обновление на отрезке за |
| Типичный вопрос | «С какими бронями конфликтует эта?» | «Сколько броней в момент ?» |
Если нужно перечислить объекты — дерево интервалов. Если нужно число — дерево отрезков, часто вместе со сжатием координат. Если все запросы известны заранее, нередко хватает заметающей прямой, и никакое дерево не нужно вовсе.
Базовые задачи на отрезки без структур данных — слияние, вставку, пересечение двух списков — я разобрал отдельно в статье про задачи на интервалы.
Где это используется в жизни
- Планировщики и календари — поиск конфликтов при бронировании.
- Геоданные и графика — R-деревья и деревья интервалов отвечают на вопрос «какие объекты попадают в окно»; одномерное дерево интервалов — частный случай этой идеи.
- Геномика — поиск генов и аннотаций, пересекающихся с участком хромосомы; деревья интервалов и их варианты используются в биоинформатических библиотеках.
- Отладка памяти — по адресу найти выделенный блок, которому он принадлежит.
- Ядро Linux — в подсистеме памяти есть дополненное красно-чёрное дерево интервалов (
interval_tree), которое используется, например, для отображений файлов в адресное пространство.
Типичные ошибки
- Неверное условие пересечения. Закрытые и полуоткрытые интервалы дают разные ответы на касаниях. Определитесь заранее и пишите
a.lo < b.hi and b.lo < a.hiдля полуинтервалов или<=для закрытых. - Забыли обновить
max_hi. Поле надо пересчитывать после каждого изменения детей: при вставке, удалении, повороте,splitиmerge. Ошибка не роняет программу, а тихо теряет ответы. - Несбалансированное дерево. Обычное BST на отсортированных вставках вырождается в список. Нужен treap, AVL или красно-чёрное дерево.
- В
any_overlapпошли не туда. Условие перехода влево —left.max_hi > lo, а не сравнение начал. Если сравнивать начала, как в обычном поиске по ключу, интервал, начавшийся давно и всё ещё длящийся, будет пропущен. - Одинаковые начала. Если ключ — только
lo, два интервала с одинаковым началом сложно различить при удалении. Ключ(lo, hi)решает проблему. - Глубокая рекурсия в Python. На сбалансированном дереве глубина , но на вырожденном рекурсивный обход упадёт с
RecursionErrorраньше, чем вы заметите, что дерево не балансируется.
Как это спрашивают на собеседовании
Реализовать дерево интервалов целиком просят редко: это долго, и в реальной работе берут готовую библиотеку. Чаще проверяют, понимаете ли вы идею:
- «Как быстро проверить, конфликтует ли новая встреча с существующими?» — ожидают дерево поиска; хороший ответ уточняет, могут ли существующие встречи пересекаться между собой.
- «Какое поле добавить в BST, чтобы искать пересечения?» —
max_hiподдерева, и почему его легко поддерживать при поворотах. - «Почему поиск одного пересечения идёт по одному пути?» — доказательство из раздела выше.
- «Чем это отличается от дерева отрезков?» — что хранится и что возвращается.
На LeetCode из этой темы стоит прорешать My Calendar I, II и III (729, 731, 732), Range Module (715) и Data Stream as Disjoint Intervals (352). В Python вместо самописного дерева в большинстве из них проходит SortedList из sortedcontainers, но проговорить, что вы бы сделали без библиотеки, — сильный плюс.
Что запомнить
- Дерево интервалов — сбалансированное дерево поиска по началам с полем в каждой вершине.
- Отсечение: поддерево с целиком левее запроса, правое поддерево вершины с целиком правее.
- Любое пересечение — один путь, ; все пересечения — .
- Центрированное дерево — статичный вариант для запросов по точке за .
- Если хранимые интервалы не пересекаются, хватит отсортированного списка и бинпоиска.