Кстати. Ты писал, что твои веревки дают копирование log(N) элементов. А в моем решении (с графом) копируется не более 2 элементов. Хоть при вставке, хоть при удалении. Да и зачем больше — путь в графе есть фактически список, а чтобы из этого списка получить новый список (новый путь в графе) путем однократного изменения , больше чем 2 элемента старого пути копировать незачем. Один слева, другой справа. Ну и еще новый элемент создать , если добавляем. Так что решение O(1).
