Есть ли способ эффективно реконструировать коллекцию на основе последовательности вставок / удалений?

Question

Примечание : приведенный ниже код выглядит как C #, но на самом деле мне будет полезен ответ на любом языке.

Предположим, а не фактическая коллекция(например, List<T>), у меня есть последовательность операций , каждая из которых выглядит примерно так:

struct ListOperation<T>
{
    public enum OperationType { Insert, Remove }

    public OperationType Type;
    public T Element; // irrelevant for OperationType.Remove
    public int Index;
}

Есть ли способ эффективно"реконструировать "коллекцию, основанную на последовательности таких операций?

В частности, я стараюсь избежать очевидной (неэффективной) реализации, заключающейся в простом создании List<T> и вызове Insert и RemoveAt- обе операции O (N) - для каждого элемента.

---

Обновление : Допустим, «последовательность» операций на самом деле представляет собой конкретную коллекцию, счет которой известен и которыйпроизвольно доступен по индексу (например, как ListOperation<T>[]).Скажем также, что фактическое количество результирующей коллекции уже известно (но на самом деле это было бы тривиально в любом случае вычислить в O (N) путем подсчета вставок и удалений).Есть другие идеи?

Answer 1

Я думаю, что вы можете сделать это в O (n lg n), используя индексированное сбалансированное двоичное дерево (двоичное дерево, где каждый узел хранит количество узлов слева и справа).С помощью этой структуры вы можете получить вставку или удаление O (lg n) в худшем случае в любой точке, пройдя по дереву, чтобы найти позицию, к которой принадлежит новый элемент, а затем выполнив все необходимые исправления для поддержания условия баланса (например,, если это красно-черное дерево, вы бы сделали исправление красно-черного дерева).

При такой настройке вы можете воспроизвести все операции в древовидную структуру, как это в O (n lg n)потому что каждая отдельная операция занимает не более O (LG N) для завершения.После того как у вас есть дерево, вы можете выполнить обход элементов по порядку, чтобы вернуть их в правильном порядке, и добавить все значения в результирующий список за O (n) время для сети O (n lg).n).

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

Answer 2

У меня есть догадка, что может существовать алгоритм O (n).

Шаг 1:

Сортировка по радикалам в цифровом виде в индексе.Занимает O (N) время.Это стабильная сортировка, если она выполняется со стороны LSB.

Шаг 2:

Допустим, есть операции с индексом i , но нет операций с меньшим индексом, который имеетне было сделано.Затем мы можем воспроизвести операции с индексом i в правильном порядке.Конкретно, что делают операции «вставка» и «удаление», мне не ясно.В худшем случае это O (n lg n) с идеями двоичного дерева, но, возможно, воспроизведение можно выполнить в O (n), потому что оно локально.

Шаг 3:

Поднятьшаг 2 к индуктивному аргументу в качестве доказательства правильности.После шагов по индексу i необходимо сохранить инвариант и более короткий список операций, поэтому по индукции ... (подробнее) ...