Эффективные структуры данных для непересекающихся целых интервалов

Question

У меня есть набор непересекающихся целых интервалов и вы хотите проверить, находится ли заданное целое число в одном из этих интервалов. Конечно, это может быть достигнуто посредством бинарного поиска в логарифмическом времени. Однако подавляющее большинство запросов возвращают false, т. Е. Только очень мало целых чисел лежат в любом интервале. Чтобы ускорить приложение, я ищу вероятностный алгоритм с постоянным временем (некая хэш-функция), которая сообщает мне, действительно ли заданное целое число не является или может быть в интервале. Вот эскиз предполагаемого алгоритма, где magic_data_structure инициализируется с интервалами, хранящихся в tree:

x = some_integer; 
if(!magic_data_structure.find(x)) 
    return false; // definitely not in any interval 
return tree.find(x); // binary search on tree 

Любые идеи или советы по литературе? Большое вам спасибо за вашу помощь!

P.S .: Кто-нибудь знает улучшения интервальных деревьев для неперекрывающихся интервалов, которые (в отличие от описанных выше) могут включать в себя другие интервалы?

Answer 1

Это наивное решение, но постоянное.

Если вы не имеете дело с чрезвычайно большими количествами чисел, вы можете просто использовать хеш-таблицу, где ключи - это числа, а значения - указатель на набор, в котором они находятся. Но, конечно, если есть много данных может занять слишком много времени (и слишком много памяти), чтобы индексировать его таким образом.

Похоже, существуют различные disjoint-set data structures and algorithms, чтобы хранить/искать их, но я сомневаюсь, что у них есть постоянное время.