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

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

Спрашивай лучше Клода, он намного больше в программировании прошарен

Ваша задача — эффективно хранить диапазоны (отрезки) и быстро выполнять:

добавление диапазона,
удаление диапазона,
поиск всех диапазонов, содержащих точку.
Дерево отрезков (segment tree) действительно не всегда эффективно для динамического добавления/удаления произвольных диапазонов. Для вашей задачи лучше подойдут следующие структуры данных:

1. Interval Tree (интервальное дерево)
Основано на сбалансированном дереве поиска (например, AVL или красно-черное дерево).
Каждый узел хранит диапазон и максимальное значение конца в поддереве.
Операции:
Добавление/удаление диапазона: O(log n)
Поиск всех диапазонов, содержащих точку: O(log n + k), где k — число найденных диапазонов.

2. Segment Tree с динамическими списками
Можно реализовать динамическое дерево отрезков, где в каждом узле хранятся списки диапазонов, полностью покрывающих этот узел.
Добавление/удаление: O(log n + k)
Поиск: O(log n + k)

3. Augmented BST (например, Order Statistic Tree)
Можно хранить интервалы в сбалансированном BST, дополнительно поддерживая максимум конца в поддереве.

Рекомендация
Для вашей задачи классическим и хорошо изученным решением является интервальное дерево (interval tree).
Оно поддерживает все нужные операции быстрее, чем за линейное время.