Структура данных для быстрого поиска местоположения

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

Должны поддерживаться следующие операции (продемонстрированы с однобуквенными строками -):

• insert(id, position)-добавить элемент с ключом idв последовательность со смещением position. Естественно, позиция каждого элемента позже в последовательности теперь увеличивается на единицу. Пример:[S E L F].insert(H, 1) -> [S H E L F]
• remove(position)-удалить элемент по смещению position. Уменьшает позицию каждого элемента позже в последовательности на единицу. Пример:[S H E L F].remove(2) -> [S H L F]
• lookup(id)-найти позицию элемента с ключом id.[S H L F].lookup(H) -> 1

Наивной реализацией будет либо связанный список, либо массив. Оба дали бы O (n)lookup, removeи insert.

На практике lookup, вероятно, будет использоваться чаще всего, причем insertи removeпроисходят достаточно часто, поэтому было бы неплохо не быть линейным (, что даст вам простая комбинация хэш-карты + массива/списка. ).

В идеальном мире было бы O (1)lookup, O (log n)insert/ remove, но я на самом деле подозреваю, что с чисто информационной -теоретической точки зрения (это не сработает, хотя я не пробовал ), так что O (log n)lookupвсе равно было бы неплохо.