σ>>https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree :
>>> Both insertion and deletion require O ( log ⁡ n ) time, with n being the total number of intervals in the tree prior to the insertion or deletion operation
DTF>А какая там сложность поиска в случае, когда надо найти все интервалы, в которые входит данная точка?
DTF>Если бы был нужен один интервал, то понятно, что логарифм.
DTF>Но мне нужны все.
Ну, очевидно же: n log n
Но, наверное, еще зависит от того, что ты с ними делать будешь ?