Начал смотреть лекцию ШАД "Задачи геометрического поиска". Там обсуждается следующая задача:
есть 3 типа запросов на прямой:
1. Добавить интервал (l..r)
2. Удалить интервал (l..r)
3. Вывести все интервалы, содержащие точку x

В лекции не стали рассказывать полное решение. Было лишь сказано, что задача решается путем построения сбалансированного дерева, ключами которого являются левые границы интервалов.

В лекции сказано, что эту задачу можно решать за асимптотику O(k + logn) на запрос 3 (и видимо за O(logn) на остальные запросы), насколько я понял.

Можете объяснить решение, которое подразумевалось в лекции, либо посоветовать литературу по этому вопросу?

Также, если предложенное в лекции решение не оптимально, то интересна оценка и доказательство асимптотики такого алгоритма.