Дерево интервалов (interval tree) и пересечение точки с множеством интервалов

Определение

Дерево интервалов (interval tree) позволяет решать следующую задачу. Дано множество отрезков [math]I=\{[x_1, x'_1], \ldots, [x_n, x'_n]\}[/math] и множество запросов. Каждый запрос характеризуется точкой [math]q_x[/math]. Для каждого запроса необходимо определить множество отрезков из [math]I[/math], которые содержат в себе [math]q_x[/math]. Построение дерева интервалов занимает время [math]O(n \log\,n)[/math], а также [math]O(n)[/math] памяти. На каждый запрос дерево интервалов позволяет отвечать за [math]O(\log\,n + k)[/math], где [math]k[/math] — размер ответа на запрос.

Построение

Чтобы построить дерево интервалов сделаем следующее. Найдем медиану множества всех координат отрезков [math]x_{mid}[/math]. Это можно сделать за [math]O(n)[/math] (см. Поиск_k-ой_порядковой_статистики_за_линейное_время). Далее разделим все отрезки на три группы: те, которые лежат строго слева (справа) от [math]x_{mid}[/math] и все остальные. Для первых двух групп рекурсивно построим дерево интервалов. Все остальные отрезки будем хранить в корне дерева. Создадим два списка отрезков, которые пересекают [math]x_{mid}[/math]. В одном отсортируем их по левой координате, в другом — по правой.

Теорема:

Дерево интервалов имеет глубину [math]O(\log\,n)[/math].

Доказательство:

[math]\triangleright[/math]

При каждом рекурсивном вызове построения дерева множество концов отрезков уменьшается более чем в два раза. Значит, после [math]O(\log\,n)[/math] рекурсивных вызовов, множество отрезков будет пусто.

[math]\triangleleft[/math]

Теорема:

Дерево интервалов занимает [math]O(n)[/math] памяти.

Доказательство:

[math]\triangleright[/math]

По построению каждый отрезок был добавлен ровно в два списка. Вершин в двоичном дереве глубины [math]O(\log\,n)[/math], очевидно, [math]O(n)[/math].

[math]\triangleleft[/math]

Теорема:

Построение дерева интервалов работает за [math]O(n\log\,n)[/math] времени.

Доказательство:

[math]\triangleright[/math]

Отдельно оценим время, которое необходимо для создания всех отсортированных списков отрезков. Т. к. их суммарная длина [math]O(n)[/math], требуется [math]O(n\log\,n)[/math] времени. Теперь рассмотрим время, необходимое для рекурсивных вызовов. Для каждой вершины дерева это время равно [math]O(m)[/math], где [math]m[/math] — количество отрезков, которые были переданы рекурсивно. Просуммируем это время по всем [math]O(\log\,n)[/math] "слоям" дерева. Под каждым слоем понимаются все вершины дерева, которые лежат на одной и той же глубине. Т. к. в каждом слое множества отрезков для любых двух вершин не пересекаются, то суммарное количество отрезков в слое равно [math]O(n)[/math]. Слоев всего [math]O(\log\,n)[/math], значит, имеем общую оценку [math]O(n\log\,n)[/math] для построения всего дерева.

[math]\triangleleft[/math]

Как отвечать на запрос?

В каждой вершине дерева хранится [math]x_{mid}[/math], ссылки на два поддерева, а также два отсортированных списка отрезков. В вершине хранятся только те отрезки, которые пересекают [math]x_{mid}[/math]. Необходимо рассмотреть два симметричных случая. Покажем, что делать в одном из них. Пусть, например, [math]q_x\gt x_{mid}[/math]. Тогда в ответ нужно добавить некоторый суффикс отрезков, которые отсортированы по правому концу. Запустимся рекурсивно от правого дерева (т. к. понятно, что никакой отрезок, который хранится в левом поддереве не может содержать [math]q_x[/math]). Аналогично разбирается случай [math]q_x \lt x_{mid}[/math].

Теорема:

Ответ на запрос происходит за [math]O(\log\,n + answer)[/math] времени.

Доказательство:

[math]\triangleright[/math]

Глубина дерева ровна [math]O(\log\,n)[/math], значит может быть только [math]O(\log\,n)[/math] рекурсивных вызовов. В каждой вершине ответ происходит за [math]O(answer)[/math], т. к. может быть просмотрен только один отрезок, который не должен быть добавлен в ответ.

[math]\triangleleft[/math]

Псевдокод

 struct interval_tree
   interval_tree *left, *right
   int x_mid
   vector<segment> left_segments, right_segments;

 interval_tree build_tree(vector<segment> segments)
   if (segment.size() == 0)
     return NULL
   x_mid = mid_element(segments.all_coordinates)
   for (segment s : segments)
     if (s.right < x_mid)
       left_child.add(s);
     if (s.left > x_mid)
       right_child.add(s);
     if (s.left <= x_mid && s.right >= x_mid)
       left_segments.add(s);
       right_segments.add(s);
   sort(left_segments) // by increasing of x_mid - segment.left
   sort(right_segments) // by increasing of segment.right - x_mid
   result.left = build(left_child);
   result.right = build(right_child);
   result.left_segments = left_segments;
   result.right_segments = right_segments;
   result.x_mid = x_mid;
   return result;

 vector<segment> get_ans(interval_tree tree, int q_x) 
   if (tree == NULL)
     return empty_result;
   if (q_x < tree.x_mid)
     result = get_ans(tree.left, q_x);
   if (q_x > tree.x_mid)
     result = get_ans(tree.right, q_x);
   if (q_x < tree.x_mid)
     it = left_segments.size() - 1;
     while (it != -1 && left_segment[it].left <= q_x)
       result.add(left_segments[it--]);
   if (q_x >= tree.x_mid)
     it = right_segments.size() - 1;
     while (it != -1 && right_segments[it].right >= q_x)
       result.add(right_segments[it--]);
   return result;