Я мечтал о структуре данных, она существует?

Мне не удалось найти эту структуру данных, но я не эксперт в этой области.

Структура реализует множество и представляет собой массив сопоставимых элементов с инвариантом. Инвариант следующий (определяется рекурсивно):

Массив длиной 1 является массивом слияния.

Массив длиной 2 ^ n (для n> 0) является массивом слияния, если:

• первая половина является массивом слияния, а вторая половина пуста или
• первый массив заполнен и отсортирован, а вторая половина является массивом слияния.

Обратите внимание, что если массив заполнен, он сортируется.

Чтобы вставить элемент, у нас есть два случая:

• Если первая половина не заполнена, вставьте рекурсивно в первую половину.
• Если первая половина заполнена, вставьте рекурсивно во вторую половину.
• После рекурсивного шага, если весь массив заполнен, объедините половинки (которые отсортированы) и измените его размер в два раза по сравнению с его первоначальной длиной.

Чтобы найти элемент, выполните рекурс в обеих половинах, используя двоичный поиск, когда массив заполнен. (Это должно быть эффективно, поскольку существует не более восходящих фрагментов).$O(\log(n))$

Структура может рассматриваться как статическая версия сортировки слиянием.

Не ясно, что нужно сделать, чтобы стереть элемент.

Изменить: после улучшения моего понимания структуры.

$A\cup B$$A$$B$$O(\log n)$$n$), но увеличивает пространство только постоянным фактором. Да, это может быть деамортизировано, благодаря Overmars и van Leeuwen, но вы действительно не хотите делать это, если вам не нужно.

Эти заметки охватывают основы.

Мешки с заброшенным кэшем - мутантное потомство деревьев Бентли-Сакс и Ван-Эмде-Боаса на стероидах.

Это похоже на деревья слияния с лог-структурой или кэширующие упускающие массивы (или COLA).

$2^k-1$$2^i$$0 \leq i < k$

$2^0$$2^1$

$O(\lg n)$$O(n)$$O(\lg^2 n)$