Существует ли структура данных для быстрой обработки списка и запросов заказа?

У нас есть набор, $L$списков элементов из множества $N = \{ 1, 2, 3, ..., n \}$, Каждый элемент из$N$ появляется в одном списке в $L$, Я ищу структуру данных, которая может выполнять следующие обновления:

1. $concat(x, y)$ : объединяет список, содержащий $y$ в конец списка, содержащего $x$

2. $split(x)$ : разбивает список, содержащий $x$ сразу после $x$

Также необходимо выполнить следующие запросы:

1. $follows(x, y)$ : возвращается $true$ если $x$ а также $y$ находятся в том же списке и $y$ идет после $x$ (но не обязательно соседствует с $x$)

2. $first(x)$ : возвращает первый элемент списка, содержащий $x$

3. $next(x)$ : возвращает следующий элемент после $x$ в списке, содержащем $x$

Я уже придумал структуру данных, которая выполняет эти обновления в $O(lg^2 (n))$ и запросы в $O(lg (n))$время. Меня больше всего интересует, существует ли уже структура данных, которая может это сделать (надеюсь, быстрее?).

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

Держите ваши целые числа в списках пропуска. Обычные списки пропусков упорядочены по ключу, но мы просто будем использовать их как представление последовательностей. Кроме того, поддерживать массив указателей размера$n$, Каждый элемент массива должен указывать на узел в списке пропуска. Я считаю, что это поддерживает$next$ в $O(1)$ и все остальные операции в $O(\lg n)$,

В частности:

• $concat$или $split$Ting два пропуска списков занимает $O(\lg n)$ время и, следовательно, делает недействительным самое большее $O(\lg n)$ указатели.
• $next$ просто следует за указателем вперед на уровне листа, принимая $O(1)$ время.
• $first$ принимает $O(\lg n)$время: следите за указателями, пока не застрянете, затем следуйте за левым указателем. Когда вы не можете больше следовать указателям слева, вы находитесь в заголовке списка пропуска. Следуйте указателям вниз до листа, затем один указатель вперед. Это первый элемент в списке.
• $follows$несколько сложнее. Действуйте как в$first$ за $y$, но запишите список значений, где вы застряли (то есть, когда вы больше не можете следить за указателями). Мы назовем этот список записанным вами «следом». Сделать то же самое для$x$, но следуйте указателям вправо, когда вы застряли, а не налево. Если$x$ предшествует $y$Их следы будут пересекаться. Следы имеют размер$O(\lg n)$, Если каждый элемент в трассе помечен застрявшим уровнем, мы можем проверить пересечение во времени$O(\lg n)$,

$next$ в худшем случае $O(1)$все остальные $O(\lg n)$ с большой вероятностью . Они могут быть сделаны в худшем случае, используя детерминированные списки пропусков.

Я думаю $concat$ может быть изготовлен $O(\lg \lg n)$используя (2,5) деревья на уровне листьев и усиливая шипы. Трюк с загрузкой см. В разделе « Чисто функциональные представления отсортированных списков, которые можно было сгенерировать ». Автор Kaplan и Tarjan.

Наименьший общий предок проблема может быть использован для решения проблемы достижимости в динамических корневых деревьев, так что я полагаю , вы будете также заинтересованы в следующих: Оптимальные алгоритмы поиска ближайшего общего Предков в динамических деревьев , по Alstrup и Thorup. Эта статья дает ограничение по времени$O(n + m \log \log n)$ за $n$ ссылки и $m$ NCA запрашивает указатель машины.