Смотрел ШАД Яндекс. Там в видео про геометрический поиск рассказывали про структуру данных интервальное дерево(interval tree). Позволяет решать следующую задачу за O(Log2N + k(размер ответа)): Дано множество отрезков и множество запросов. Каждый запрос характеризуется точкой. Для каждого запроса необходимо определить множество отрезков, которые содержат в себе эту точку. Я не понял, как оно строится. На Wiki тоже ничего не понял. Кто-нибудь знает что-нибудь о ней