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

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

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


DTF>Хотелось бы, чтобы эти операции работали быстрее, чем за линейное время.
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). 
Оно поддерживает все нужные операции быстрее, чем за линейное время.

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

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

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


DTF>Хотелось бы, чтобы эти операции работали быстрее, чем за линейное время.
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). 
Оно поддерживает все нужные операции быстрее, чем за линейное время.