Определить, находится ли целое число в нескольких диапазонах целых чисел

Question

Допустим, у вас есть целое число n, Допустим, у вас есть список непересекающихся целочисленных диапазонов, например:

1-9
99-105
160-205
503-600
// many more thousands of ranges, etc ....

Я мог бы очень легко перебрать все это и проверить, находится ли n между каждой из границ, и вернуть true, если он есть. Это было бы O(n), что плохо. Можно ли это сделать в O(1)?

Некоторые правила:

• Сами целые числа очень велики, а диапазоны очень широки, поэтому было бы невозможно просто получить полный список допустимых целых чисел и использовать что-то вроде Set для поиска O (1). Хранение такого количества целых чисел в памяти слишком дорого. Я могу только хранить список границ.
• Я собираюсь запустить этот тест много раз, поэтому я могу заранее преобразовать список в некоторую структуру данных, если это сделает последующие поиски более эффективными.

Я чувствую, что могу получить двоичные представления этих диапазонов и построить дерево, которое даст O(log(n)).

Мой реальный вопрос

У меня есть список IP-адресов подсетей. Мне нужно проверить, есть ли данный IP в любой из этих подсетей. У меня будет много много IP-адресов для проверки. Я могу конвертировать IP в целое число (1.2.3.4 => 1*2^32 + 2*2^16 + 3*2^8 + 4). И я могу конвертировать подсети аналогично. Это приравнивается к вопросу "проще объяснить" выше.

Спасибо!

Answer 1

Сохранение диапазонов в отсортированном векторе и поиск значения с помощью std::lower_bound - это O(log(n)).

Какой размер целого числа вам нужен для IP 200.200.200.200 с этим алгоритмом? Почему не только 200200200200?

Дерево четырех ветвей для IP ABCD для хранения подсетей кажется более подходящим.