Поиск всех интервалов, которые не пересекаются с точкой

Question

У меня есть интервалы в форме (a1, b1), (a2, b2), ...., (an, bn).
Я хотел бы поддержать следующие операции

1. Добавление нового интервала.
2. Удаление существующего интервала.
3. Учитывая точку, найдите все интервалы, которые не пересекаются с точкой.

Дерево интервалов - это простое решение, если мы хотим найти интервалы, которые пересекаются с точкой. Как насчет случая, когда мы хотим найти непересекающиеся интервалы?

Answer 1

У всех узлов на двух деревьях одновременно. Дерево A удерживает их ключом ai, а дерево B удерживает их ключом bi.
Вставка и удаление, очевидно, O(log n).
Для требования 3 напечатайте узлы в B от наименьшего до самого большого и остановитесь, когда bi все еще меньше, чем точка. То же самое, но в обратном направлении, в А.

Пример:
Учитывая (1,10), (5,18), (13,20) и точку 12.
Интервал (ы) в A, где ai больше, чем 12 - (13,20), а в B - меньший интервал (ы), (1,10).