Есть ли эквивалент деревьев Ван Эмде Боаса для канатов?

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

Деревья Van Emde Boas - это почти самые быстрые очереди с приоритетами, если вы не возражаете против верхней границы количества предметов, которые вы можете поместить в нее, и больших затрат на инициализацию. Мой вопрос заключается в том, существует ли какая-либо структура данных, которая столь же быстра, как дерево Ван Эмде Боаса, но поддерживает операции текстового редактора.

Нам нужно только поддерживать до символов в нашей структуре данных (поэтому, если log m = 32 , мы поддерживаем до 4 ГБ символов ASCII). Нам разрешено $m$$\log m = 32$ времячтобы инициализировать новую структуру данных. Мы хотели бы поддержать следующие операции:$\sqrt{m}$

• Вставьте символ в позиции в O ( log log m ) (и, таким образом, увеличивая позицию каждого последующего символа на 1).$i$$O(\log \log m)$
• Удалить символ в позиции в O ( log log m ) .$i$$O(\log \log m)$
• Вернуть символ в позиции в O ( log log m ) .$i$$O(\log \log m)$

Таким образом, вставка (0, 'a') и вставка (0, 'b') приводят к "ba".

Еще лучше было бы это:

• Вернуть указатель на некоторый индекс в O ( log log m ) .$i$$O(\log \log m)$
• Получив указатель, верните символ в этой позиции в .$O(1)$
• Используя указатель, удалите символ в этой позиции в .$O(1)$
• Используя указатель, добавьте символ в этой позиции в и верните указатель в следующую позицию.$O(1)$
• (необязательно) При наличии «указателя» вернуть «указатель» на следующий / предыдущий символ в .$O(1)$

Фредман и Сакс показывают в «Сложности проверки ячеек динамических структур данных», что вы не можете сделать лучше, чем амортизированное время для операций, которые вы ищете. Они называют эту проблему «представлением списка».$\Theta\left(\frac{\lg m}{\lg \lg m}\right)$

Дитц представил структуру данных в «Оптимальных алгоритмах для индексации списка и ранга подмножества», которая достигает этой границы.