Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
Версия от 18:44, 7 января 2014; Qwerty787788 (обсуждение | вклад) (Новая страница: «{{notready}} == Определение == Дерево интервалов (interval tree) позволяет решать следующую задачу. Да...»)
Конспект не готов. |
Определение
Дерево интервалов (interval tree) позволяет решать следующую задачу. Дано множество отрезков
и множество запросов. Каждый запрос характеризуется точкой . Для каждого запроса необходимо определить множество отрезков из , которые содержат в себе . Построение дерева интервалов занимает время , а также памяти. На каждый запрос дерево интервалов позволяет отвечать за , где — размер ответа на запрос.