Дерево интервалов (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] — размер ответа на запрос.