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

Question

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

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

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

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

---

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

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

---

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

Answer 1

Что ж, любой вид самобалансирующегося двоичного дерева (например, красно-черный) обеспечит все три операции для O(logn). Карта C ++ RB , упомянутый является одним из примеров (если я полностью не забыл C ++).

Что касается индексации (операция get), есть стандартная хитрость. Мы будем хранить в каждом узле, сколько узлов имеет его левое поддерево. Теперь мы можем найти элемент в позиции i за O(logn) времени следующим образом

Data get(Node root, int i) {
    if (i <= root.leftCount) {
        return get(root.left, i);
    } else if (i == root.leftCount + 1) {
        return node;
    } else {
        return get(root.right, i - root.leftCount - 1);
    }
}

Очевидно, что каждый раз, когда элемент добавляется или удаляется, leftCount значения придется пересчитывать, но это нужно делать только для O(logn) узлов. (подумайте, сколько узлов включает удаленный один в своем левом поддереве - только те, которые находятся непосредственно между ним и корнем)

Answer 2

Список пропуска может выполнять вставку / удаление / поиск индекса каждый в O(log n): http://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist

Для O(n^1/2) вставки / удаления и O(1) индекса я предполагаю что-то вроде C ++ deque, но состоящее из n^1/2 смежных блоков, каждый из n^1/2 элементов (+/- 1 на каждый квадратный корень, конечно). Чтобы удалить, вы должны перетасовать часть блока, содержащего удаленный элемент (O(n^1/2)), а затем перетасовать вниз целый старших блоков, что вы должны сделать, настроив смещение для каждого блокировать (не более O(n^1/2) блоков), а не перемещать что-либо. Чтобы вставить, вам, возможно, придется перераспределить блок (O(n^1/2)) и отрегулировать смещения. В обоих случаях вам также может понадобиться сдвинуть один или два элемента от начала / конца некоторых блоков к концу / началу предыдущего / следующего блока, опять же самое большее O(n^1/2) раз, чтобы сохранить инвариант, что нет двух блоков отличаются по размеру более чем на 1, за исключением последнего, который используется для устранения провисания. Наконец, вам иногда приходится создавать или уничтожать блок. Функция поиска равна O(1), поскольку вы можете попасть в один блок искомого элемента за одно деление, а затем просмотреть сохраненные смещения для одного или двух блоков, чтобы найти его.

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