Изменения

== Определение ==

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