Здравствуйте, DTF, Вы писали:

bnk>>Поиск всех диапазонов, содержащих точку: O(log n + k), где k — число найденных диапазонов.

DTF>Вот я не понимаю, откуда там O(log n + k) ?

Там (в википедии) ноды сложные. Фактически, нода содержит почти готовый ответ (множество интервалов, не один интервал).

Здравствуйте, DTF, Вы писали:

DTF>Всем привет.
DTF>Нужна помощь коллег.

DTF>Я ищу структуру данных, которая хранит в себе диапазоны, задаваемые координатой начала и конца, и поддерживает операции
DTF> * добавить диапазон
DTF> * удалить диапазон
DTF> * Найти все диапазоны, содержащие некоторую точку.


DTF>Хотелось бы, чтобы эти операции работали быстрее, чем за линейное время.
DTF>Гугл предлагает дерево отрезков, но, если я правильно понимаю, добавление и удаление там в худшем случае будет как раз линейным.

DTF>В общем, нужна помощь коллективного разума

Очень похоже на тестовое в thinkcell — можете посмотреть решения в интернете.