Дерево интервалов: как быстро находить пересекающиеся отрезки

Дерево интервалов простыми словами: дерево поиска с полем max_hi, поиск любого и всех пересечений, центрированное дерево для точек, My Calendar I и II на Python и сравнение с деревом отрезков.

13 мин чтенияалгоритмы · деревья · интервалы · python

Коротко

ЧтоСуть
ЗадачаХранить набор интервалов и быстро находить те, что пересекаются с запросом
Главная идеяДерево поиска по началам интервалов, в каждой вершине — максимум концов в её поддереве
СложностьВставка и удаление O(log⁡n)O(\log n), «есть ли пересечение» O(log⁡n)O(\log n), все kk штук — O(klog⁡n)O(k \log n)
Центрированный вариантСтатичный набор, запрос «какие интервалы содержат точку» за O(log⁡n+k)O(\log n + k)
Где спрашиваютMy Calendar I/II/III, Range Module, планировщики, базы геоданных, отладчики памяти
  • Дерево интервалов — это не новая структура с нуля, а дополненное дерево поиска: к обычному сбалансированному дереву добавляется одно поле.
  • Если интервалы в наборе не пересекаются друг с другом, дерево интервалов не нужно: хватит отсортированного списка и бинпоиска.

Какую задачу решаем

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

  1. Добавить или удалить интервал.
  2. Найти интервалы, которые пересекаются с отрезком [lo,hi)[lo, hi), — любой один или все.

Везде ниже интервалы полуоткрытые: [lo,hi)[lo, hi), начало входит, конец нет. Так встреча с 10 до 20 и встреча с 20 до 30 не конфликтуют. Два полуинтервала пересекаются тогда и только тогда, когда

a.lo<b.hiиb.lo<a.hi.a.lo < b.hi \quad \text{и} \quad b.lo < a.hi.

Это условие стоит выучить наизусть: в нём нет ни одного «или», и его легко проверить на случаях «один внутри другого», «касаются концами» и «один левее другого».

Наивные решения

Список и перебор. Храним интервалы в списке, на запрос проверяем все. Вставка O(1)O(1), запрос O(n)O(n). При 10510^5 операций — 101010^{10} проверок, слишком медленно.

Сортировка по началу. Если отсортировать интервалы по lo, бинпоиском можно отрезать все интервалы с lo≥hiзапросаlo \ge hi_{запроса}: они точно правее. Но с другой стороны отсечь нечего. Интервал, начавшийся очень давно, может тянуться до сих пор, и чтобы его найти, придётся просмотреть всё, что левее. Худший случай — снова O(n)O(n).

Именно эта асимметрия и подсказывает решение: по началам мы умеем отсекать, а про концы нам нужна сводка — «есть ли где-то в этой части набора интервал, который заканчивается достаточно поздно».

Идея: дерево поиска плюс максимум концов

Возьмём двоичное дерево поиска с ключом lo (при равных началах — пара (lo, hi)). В каждой вершине, кроме самого интервала, храним

max_hi(v)=max⁡(v.hi, max_hi(v.left), max_hi(v.right)),max\_hi(v) = \max\bigl(v.hi,\ max\_hi(v.left),\ max\_hi(v.right)\bigr),

то есть самый поздний конец среди всех интервалов поддерева.

Это поле даёт ровно то отсечение, которого не хватало:

  • если max_hi(v)≤loзапросаmax\_hi(v) \le lo_{запроса}, все интервалы поддерева заканчиваются до начала запроса — туда не идём;
  • если v.lo≥hiзапросаv.lo \ge hi_{запроса}, то и сама вершина, и всё её правое поддерево (там начала ещё больше) начинаются после конца запроса — правое поддерево не нужно.

Поле max_hi пересчитывается локально, из самой вершины и двух детей. Поэтому его легко поддерживать при любых изменениях дерева: после вставки, удаления или поворота достаточно пересчитать его у изменившихся вершин снизу вверх. Это общее свойство дополненных деревьев, на нём же держатся размеры поддеревьев в порядковой статистике.

Почему нужна балансировка

Все оценки O(log⁡n)O(\log n) верны только для сбалансированного дерева. Если вставлять интервалы в порядке возрастания начал — а брони в календаре часто так и приходят, — обычное BST выродится в список, и всё снова станет O(n)O(n).

В учебнике Кормена дерево интервалов строят на красно-чёрном дереве. Для собеседования и для 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. Мы идём влево. Рассмотрим два случая.

  1. В левом поддереве есть пересечение — отлично, найдём его там.
  2. В левом поддереве пересечений нет. Но там есть интервал w, у которого w.hi = v.left.max_hi > lo. Раз он не пересекает запрос, а конец у него правее lo, значит, он целиком правее: w.lo >= hi. Все интервалы правого поддерева начинаются не раньше w.lo — они тоже правее запроса. Значит, пересечения нет нигде, и ответ None верен.

А если v.left.max_hi <= lo, левое поддерево целиком заканчивается до запроса, и идти туда бессмысленно. Так на каждом шаге отбрасывается одна из половин, и поиск занимает O(h)O(h), то есть O(log⁡n)O(\log n) для сбалансированного дерева.

Сложность

ОперацияВремяКомментарий
Вставка, удалениеO(log⁡n)O(\log n)ожидаемо, для декартова дерева
Есть ли пересечениеO(log⁡n)O(\log n)один путь от корня
Все пересеченияO(min⁡(n,klog⁡n))O(\min(n, k \log n))kk — размер ответа
ПамятьO(n)O(n)одно дополнительное число на вершину

Оценка для всех пересечений получается так: каждый найденный интервал «оплачивает» не больше одного пути длины O(log⁡n)O(\log n) к себе, а поддеревья без ответов отсекаются сразу на входе. Поиск всех пересечений можно ускорить до O(log⁡n+k)O(\log n + k) на других структурах, но для дерева с одним полем max_hi это честная граница.

Центрированное дерево интервалов

Есть второй классический вариант, который в литературе тоже называют деревом интервалов. Он работает для статичного набора и отвечает на вопрос «какие интервалы содержат точку xx» — так называемый stabbing query.

Построение рекурсивное:

  1. Выбираем центр cc — медиану начал интервалов.
  2. Делим интервалы на три группы: целиком левее cc, целиком правее cc и те, что содержат cc.
  3. Интервалы, содержащие центр, храним в вершине в двух списках: по возрастанию начала и по убыванию конца.
  4. Левую и правую группы обрабатываем рекурсивно.

Хитрость в запросе. Пусть x<cx < c. Все интервалы в вершине содержат cc, значит, их концы правее xx — проверять нужно только начало. Идём по списку, отсортированному по началу, и останавливаемся на первом, который начинается правее xx: дальше начала только больше. Симметрично для x≥cx \ge c идём по списку концов.

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)) # []

Деталь, на которой я сам споткнулся в первой версии: центр берётся из начал, а не из всех концов подряд. Если взять медиану всех точек, центр может совпасть с концом интервала, например c=4c = 4 для (3, 4). Тогда этот интервал по правилу полуоткрытости «целиком левее», уходит в левую группу, там центр снова выпадает на 4 — и рекурсия бесконечна. Медиана начал гарантирует, что хотя бы один интервал останется в вершине, а каждая из боковых групп содержит не больше половины интервалов. Отсюда глубина O(log⁡n)O(\log n).

Каждая вершина на пути запроса тратит O(1)O(1) на неудачную проверку плюс O(1)O(1) на каждый найденный интервал, поэтому запрос — O(log⁡n+k)O(\log n + k). Построение — O(nlog⁡n)O(n \log n), если сортировать один раз и аккуратно раздавать уже отсортированные списки детям; в коде выше для простоты сортировка повторяется на каждом уровне, это O(nlog⁡2n)O(n \log^2 n).

Минус центрированного дерева — вставлять и удалять интервалы в нём неудобно. Поэтому для динамических задач берут дополненное дерево поиска, а центрированное — для заранее известного набора, например при подготовке геометрических данных.

Задача: My Calendar I

LeetCode 729. Нужно реализовать календарь: метод book(start, end) добавляет бронь [start,end)[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 (максимальная кратность пересечений) удобнее дерево отрезков с отложенными операциями или подсчёт событий заметающей прямой: там нужны не сами интервалы, а число слоёв в каждой точке.

Дерево интервалов или дерево отрезков

Названия похожи, и на собеседовании их иногда путают. Разница принципиальная.

ВопросДерево интерваловДерево отрезков
Что хранитСами интервалы, по одному в вершинеАгрегат (сумма, максимум) над ячейками массива
Что возвращаетКонкретные пересекающиеся интервалыЧисло: сумму, максимум, покрытие на отрезке
КоординатыЛюбые, хоть вещественныеИндексы массива, большие — через сжатие координат
Изменение набораВставка и удаление за O(log⁡n)O(\log n)Обновление на отрезке за O(log⁡n)O(\log n)
Типичный вопрос«С какими бронями конфликтует эта?»«Сколько броней в момент tt?»

Если нужно перечислить объекты — дерево интервалов. Если нужно число — дерево отрезков, часто вместе со сжатием координат. Если все запросы известны заранее, нередко хватает заметающей прямой, и никакое дерево не нужно вовсе.

Базовые задачи на отрезки без структур данных — слияние, вставку, пересечение двух списков — я разобрал отдельно в статье про задачи на интервалы.

Где это используется в жизни

  • Планировщики и календари — поиск конфликтов при бронировании.
  • Геоданные и графика — R-деревья и деревья интервалов отвечают на вопрос «какие объекты попадают в окно»; одномерное дерево интервалов — частный случай этой идеи.
  • Геномика — поиск генов и аннотаций, пересекающихся с участком хромосомы; деревья интервалов и их варианты используются в биоинформатических библиотеках.
  • Отладка памяти — по адресу найти выделенный блок, которому он принадлежит.
  • Ядро Linux — в подсистеме памяти есть дополненное красно-чёрное дерево интервалов (interval_tree), которое используется, например, для отображений файлов в адресное пространство.

Типичные ошибки

  1. Неверное условие пересечения. Закрытые и полуоткрытые интервалы дают разные ответы на касаниях. Определитесь заранее и пишите a.lo < b.hi and b.lo < a.hi для полуинтервалов или <= для закрытых.
  2. Забыли обновить max_hi. Поле надо пересчитывать после каждого изменения детей: при вставке, удалении, повороте, split и merge. Ошибка не роняет программу, а тихо теряет ответы.
  3. Несбалансированное дерево. Обычное BST на отсортированных вставках вырождается в список. Нужен treap, AVL или красно-чёрное дерево.
  4. В any_overlap пошли не туда. Условие перехода влево — left.max_hi > lo, а не сравнение начал. Если сравнивать начала, как в обычном поиске по ключу, интервал, начавшийся давно и всё ещё длящийся, будет пропущен.
  5. Одинаковые начала. Если ключ — только lo, два интервала с одинаковым началом сложно различить при удалении. Ключ (lo, hi) решает проблему.
  6. Глубокая рекурсия в Python. На сбалансированном дереве глубина O(log⁡n)O(\log n), но на вырожденном рекурсивный обход упадёт с 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, но проговорить, что вы бы сделали без библиотеки, — сильный плюс.

Что запомнить

  • Дерево интервалов — сбалансированное дерево поиска по началам с полем max_himax\_hi в каждой вершине.
  • Отсечение: поддерево с max_hi≤lomax\_hi \le lo целиком левее запроса, правое поддерево вершины с v.lo≥hiv.lo \ge hi целиком правее.
  • Любое пересечение — один путь, O(log⁡n)O(\log n); все пересечения — O(klog⁡n)O(k \log n).
  • Центрированное дерево — статичный вариант для запросов по точке за O(log⁡n+k)O(\log n + k).
  • Если хранимые интервалы не пересекаются, хватит отсортированного списка и бинпоиска.

Потренироваться в спокойной обстановке

Все задачи