81
правка
Изменения
Нет описания правки
== Определение ==
Дерево интервалов (interval tree) позволяет решать следующую задачу. Дано множество отрезков <tex>I=\{[x_1, x'_1], \ldots, [x_n, x'_n]\}</tex> и множество запросов. Каждый запрос характеризуется точкой <tex>q_x</tex>. Для каждого запроса необходимо определить множество отрезков из <tex>I</tex>, которые содержат в себе <tex>q_x</tex>. Построение дерева интервалов занимает время <tex>O(n \log\,n)</tex>, а также <tex>O(n)</tex> памяти. На каждый запрос дерево интервалов позволяет отвечать за <tex>O(\log\,n + k)</tex>, где <tex>k</tex> {{---}} размер ответа на запрос.
Глубина дерева ровна <tex>O(\log\,n)</tex>, значит может быть только <tex>O(\log\,n)</tex> рекурсивных вызовов. В каждой вершине ответ происходит за <tex>O(answer)</tex>, т. к. может быть просмотрен только один отрезок, который не должен быть добавлен в ответе.
}}
== Псевдокод ==
<code>
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;
</code>
