Какую структуру данных можно использовать для хранения и извлечения диапазонов дискретных значений?
У меня есть программа на JavaScript, в которой я буду управлять множеством диапазонов целых чисел.. В этом контексте диапазон — это просто начальное и конечное значение (или что-то эквивалентное, например, начальное и конечное значение )со ссылкой на другой объект. Диапазоны могут перекрываться и быть идентичными (, хотя объект, на который делается ссылка, будет другим ).
Возможные начальные и конечные значения находятся в диапазоне от 0 до 4294967295 (2 32-1 или0xFFFFFFFF), хотя в домене есть несколько больших «дыр», которые ни один диапазон никогда не закроет, даже частично. Большинство диапазонов будут очень малы по сравнению с областью возможностей. :Я ожидаю, что подавляющее большинство будет иметь длину меньше 2000.
Наиболее важным вариантом использования этой структуры будет поиск всех диапазонов, содержащих заданное целочисленное значение. В большинстве случаев я ожидаю, что поиск завершится ошибкой (не будет диапазона, содержащего заданное значение ).
В противном случае мне, очевидно, также нужно будет добавлять в него элементы (часто )и удалять из него элементы (редко ). Время от времени мне также нужно будет найти все диапазоны, перекрывающие заданный диапазон, а не все диапазоны, содержащие одно значение.
Какую структуру данных я могу использовать для этого? Линейный поиск в списке диапазонов нецелесообразен, потому что в большинстве случаев поиск терпит неудачу; и мне нужно делать поиски очень, очень часто.