Алгоритмическая загадка: последовательность с произвольным доступом, вставкой и удалением

Опишите структуру данных, где:

• Любой элемент индексируется целым значением, как в массиве
  • целое число может индексировать одно значение
  • целые числа, используемые для индексации элементов, являются смежными : они идут от 1 до n без отверстий
• Получение элемента в позиции i (то есть: связанный элемент к целому числу i ) должно быть как можно быстрее
  • произвольный доступ
• Вставка нового элемента в позицию i должна выполняться как можно быстрее
  • это будет правильно -сдвиг любого элемента из i и далее
• Удаление элемента в позиции i также должно быть как можно быстрее
  • это сдвинет влево любой элемент из i + 1 и далее

РЕДАКТИРОВАТЬ: кое-что, о чем я забыл: индексы предметов можно сдвигать только при добавлении / удалении, их нельзя менять местами случайным образом.

В этом описании n - это размер структуры (то есть: сколько элементов она содержит), а i - общее целое число (1 <= i <= n ), конечно.

Я слышал это от парня, которого встретил на моем факультете. Не знаю, вопрос ли это на собеседовании, вопрос на экзамене, просто загадка или что-то в этом роде, но я думаю, это может быть все.

Если я правильно помню (но это было до 24 декабря), он сказал, что такая структура данных может быть реализована либо с помощью O (sqrt n) вставки / удаления, либо O (1) время доступа или с O (log n) для любой операции.

РЕДАКТИРОВАТЬ: Было дано несколько правильных ответов. Прочтите, если не хотите больше думать об этой проблеме.