Структура данных для эффективного поиска целых чисел в диапазоне запросов

Question

Существует произвольное количество различных целочисленных значений без знака в пределах известного диапазона .

Число целых значений равно << числоцелые числа в диапазоне. </strong>

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

1. Вставка в O (1)
2. Послевставка выполнена:
   • Удаление в O (1)
   • Получить все значения в пределах диапазона запроса в O (k), где k - это число значений результата (возвращаемые значения не должны бытьотсортировано)

Сложность памяти не ограничена.Однако астрономически большой объем памяти недоступен; -)

Вот пример:

• range = [0, 1023]
• insert 42
• вставка 350
• вставка 729
• вставка 64
• вставка 1
• вставка 680
• вставка 258
• найти значения в [300; 800];возвращает {350, 729, 680}
• удалить 350
• удалить 680
• найти значения в [35; 1000];возвращает {42, 258, 64, 729, 258}
• удалить 42
• удалить 258
• найти значения в [0;5];возвращает {1}
• удалить 1

Возможна ли такая структура данных?(с помощью справочных таблиц и т. д.)?

Приближение Я думал о том, что будет:

• Ячейки вставленных значений в сегменты,0..31 => корзина 0, 32..63 => корзина 1, 64..95 => корзина 2, 96..127 => корзина 3, ...

• Вставка: найти идентификатор сегмента, используя простую арифметику сдвига, а затем вставить его в массив для каждого сегмента

• Найти: найти идентификатор сегмента начальной и конечной точки, используя арифметику сдвига.Просмотрите все значения в первом и последнем сегменте и проверьте, находятся ли они в пределах диапазона или вне диапазона.Добавить все значения во всех промежуточных сегментах к результату поиска

• Удалить: найти идентификатор сегмента с помощью сдвига.Поменяйте местами значение для удаления с последним значением в сегменте, а затем уменьшите счетчик для этого сегмента.

Недостаток: если есть много запросов, которые запрашивают диапазон, имеющий диапазон менее 32 значений,Вся корзина будет проверяться каждый раз.

Недостаток 2: если в диапазоне есть пустые корзины, они также будут посещаться на этапе поиска.

Answer 1

Теоретически, дерево Ван Эмде Боаса - ваша лучшая ставка с операциями времени O (log log M), где M - размер диапазона.Использование пространства довольно велико, хотя есть и более эффективные варианты.

На самом деле теоретический уровень техники описан в статье Об отчете о дальности в одном измерении , Мортенсена, Паг и Патраску.

Я не уверен, что существующие нижние границы исключают O (1), но M не будет достаточно большим, чтобы сделать различие существенным.Вместо структуры vEB я бы просто использовал k-арное дерево со степенью k, равной двум, например 32 или 64.

РЕДАКТИРОВАТЬ: вот один из способов поиска по диапазону с помощью дерева.

Давайте предположим, что каждый элемент данных является небольшим шаблоном (достаточно просто; так думает процессор).Каждое поддерево состоит из всех узлов с определенным префиксом.Например, {0000, 0011, 0101, 1001} представлен следующим 4-мя числами, где X обозначает нулевой указатель.

+---+---+---+---+
|00\|01\|10\|11X|
+--|+--|+--|+---+
   |   |   |
   |   |   +----------------------------+
+--+   |                                |
|      +------------+                   |
|                   |                   |
v                   v                   v
+---+---+---+---+   +---+---+---+---+   +---+---+---+---+
|00\|01X|10X|11\|   |00X|01\|10X|11X|   |00X|01\|10X|11X|
+--|+---+---+--|+   +---+--|+---+---+   +---+--|+---+---+
   |           |           |                   |
   v           v           v                   v
  0000        0011        0101                1001

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

+--------+--------+--------+--------+
|00(1001)|01(0100)|10(0100)|11(0000)|
+--------+--------+--------+--------+

Для поиска по деревудиапазон, как [0001, 1000], мы начинаем с корня, определяем, какие поддеревья могут пересекать диапазон, и рекурсировать по ним.В этом примере соответствующие дочерние элементы корня - 00, 01 и 10. Соответствующие дочерние элементы 00 - это поддеревья, представляющие префиксы 0001, 0010 и 0011.

Для фиксированного значения k, отправка отчета из k-три три - O (log M + s), где M - количество битовых комбинаций, а s - количество совпадений.Не обманывайте себя - когда k средний, каждый узел занимает пару строк кеша, но время не очень велико, поэтому количество пропусков кеша довольно мало.

Answer 2

Вы могли бы достичь своей цели (O (1), O (1) и O (k)), если операция запроса требовала, чтобы ей было сказано значение хотя бы одного существующего члена, который уже находится в соответствующем диапазоне (нижняя граница возможно).Можете ли вы предоставить гарантию, что вы уже знаете хотя бы одного члена ассортимента?Я думаю, нет.Я буду расширять, если вы можете.

Теперь я сосредоточусь на проблеме, как указано.Каждое число в структуре данных должно составлять часть связанного списка, так что каждое число знает следующее наибольшее число, которое находится в структуре данных.В C ++

struct Number {
    struct Number *next_highest;
    int value;
};

Очевидно, что наибольшее значение в наборе будет иметь next_highest==NULL, но в противном случае this->value < this->next_highest->value

Чтобы добавить, удалить или запросить, нам нужно найтисуществующие Number s, которые близки к определенному значению поиска.

set<Number *, specialized_comparator_to_compare_on_value_t >

Вставка и удаление будет O (log (N)), а запрос будет O (log (N) + k),N - это число значений в настоящее время в наборе, которое, как вы говорите, будет намного меньше, чем M (количество возможных значений соответствующего типа данных).Следовательно, log (N)