Структура данных для обработки интервалов
У меня есть серия временных интервалов (t_start, t_end), который не может наложиться, т.е.: t_end (i)> t_start (i+1). Я хочу сделать следующие операции:
1) Добавьте новый (Объединение) интервалы [{(1,4), (8,10)} U (3,7) = {(1,7), (8,10)}]
2) Выньте интервалы [(1,7) - (3,5) = {(1,3), (5,7)}
3) Проверка, накладываются ли точка или интервал с интервалом в моем ряду (пересечение)
4) Нахождение первого "неинтервала" минимальной длины после некоторой точки [{(1,4), (7,8)}: существует "неинтервал" длины 3 между 4 и 7].
Я хочу знать хорошие способы реализовать это, с низкими сложностями (зарегистрируйтесь, n для всех операций сделал бы это).
Связанный вопрос: Структура данных для быстрого временного интервала ищет
2 ответа
Похоже, что можно просто использовать сбалансированное двоичное дерево всех граничных времен.
Например, представить {(1,4), (8,10), (12,15)} в виде дерева, содержащего 1, 4, 8, 10, 12 и 15.
Каждый узел должен сказать, является ли он началом или концом интервала. Итак:
8 (start)
/ \
1 (start) 12 (start)
\ / \
4 (end) 10 (end) 15 (end)
(Здесь все "конечные" узлы заканчиваются внизу по стечению обстоятельств.)
Тогда, я думаю, все ваши операции могут быть произведены во времени O(log n). Добавить интервал:
Найти время начала. Если оно уже есть в дереве в качестве времени старта, вы можете оставить его там. Если оно уже в дереве в качестве времени окончания, то его нужно удалить. Если его нет в дереве и , оно не выпадает в течение существующего интервала, Вы захотите его добавить. Иначе вы не захотите его добавлять.
Найдите время остановки, используя тот же самый метод, чтобы узнать, нужно ли добавить его, удалить или нет.
Теперь вы просто хотите добавить или удалить вышеупомянутые начальные и конечные узлы и в то же время удалить все существующие узлы между ними. Для этого вам нужно перестроить узлы дерева на этих двух местах дерева или непосредственно над . Если высота дерева O(log n), которую вы можете гарантировать с помощью сбалансированного дерева, то это займет время O(log n).
(Disclaimer: Если вы на Си++ и занимаетесь явным управлением памятью, то в конечном итоге вы можете освободить больше O(log n) фрагментов памяти, но на самом деле, я думаю, что время, необходимое для освобождения узла, должно быть выставлено в счет тому, кто его добавил.)
Удаление интервала в значительной степени одно и то же.
Проверка точки или интервала проста.
Поиск первого промежутка хотя бы заданного размера после заданного времени можно выполнить и в O(log n), если также кэшировать еще два кэша информации на узел:
В каждом стартовом узле (кроме крайнего левого) размер промежутка сразу слева.
В каждом узле - размер наибольшего промежутка, который появляется в этом поддереве.
Чтобы найти первый промежуток заданного размера, который появляется через заданное время, сначала найдите этот промежуток в дереве. Затем поднимитесь вверх, пока не достигнете узла, в котором, как утверждается, находится достаточно большой разрыв. Если вы поднялись справа, вы знаете, что этот промежуток находится слева, поэтому игнорируйте его и продолжайте идти вверх. Иначе вы подошли слева. Если узел является стартовым, проверьте, достаточно ли большой разрыв слева от него. Если да, то вам конец. В противном случае, достаточно большой зазор должен быть где-то справа. Спуститесь вправо и продолжайте вниз, пока не найдете зазор. Опять же, потому что высота дерева - O(log n), ходить по нему три раза (вниз, вверх и, возможно, снова вниз) - O(log n).
Не зная больше специфики, я бы посоветовал прочитать о Interval Trees. Деревья интервалов представляют собой особый 1-мерный случай более общих kd-деревьев и имеют O(n бревно n) типичное время построения, а также O(n бревно n) типичное время работы. Точные реализации алгоритмов Вам необходимо будет найти самим, но Вы можете начать с просмотра CGAL.