\Section{Rope}{20 марта}{Михаил Шавкунов}  

\Subsection{Определение}

Rope -- интерфейс для структуры данных, позволяющий резать строку на подстроки и склеивать их в другом порядке. 

Как мы умеем решать эту задачу?\\
Заметим, что строку можно интерпретировать как массив, на массиве умеем строить дерево, а значит через операции Split и Merge мы можем осуществить то, что нам нужно. Т.е. просплитить в нужном месте, а затем склеить в другом порядке.

Split и Merge мы умеем делать в следующих структурах:

\begin{MyList}

\item Treap. Декартово дерево по неявному ключу.

\item Через Splay. Ниже будет приведено описание Split и Мerge.

\item Через Skip-List.

\item Также утверждается, что в AVL и 2-3 Tree также можно реализовать Split и Merge.

\end{MyList}

\vspace*{-0.5em}
\Subsection{Через Splay}

\Subsubsection{Split}

Пусть мы хотим сделать split по элементу $x$.
Можно найти его lowerbound($x$) и вытолкнуть его в корень. Второй способ это добавить его в дерево, он автоматически будет корнем в новом дереве, тогда левое и правое поддеревья -- есть ответ функции Split.
Понятно, что оба способа работают за логарифм.

\Subsubsection{Merge}

Нам даны дерево $L$ и $R$. Считаем, что они оба корректны.
Найдем самый правый элемент в левом поддереве и поднимем его в корень. Это мы сделали, чтобы операция Merge вообще просто работала за $O(1)$, проводя ссылку в корень дерева $R$. Таким образом это тоже работает за $O(\log n).$

\Subsection{Skip-List}

Рандомизированная структура данных. Не является деревом, но умеет делать такие же операции со строками.\\
Собственно, что это такое: пусть мы храним отсортированный массив как список. Сделаем второй уровень: каждый элемент на втором уровне окажется с вероятностью $\frac{1}{2}$. Аналогично сделаем на последующих уровнях. Если высота уровня равна m, то вероятность, что конкретный элемент там окажется -- $\frac{1}{2^m}$. Для удобства реализации, можно договориться, чтобы левый элемент всегда переходил на вверх.

Сколько мы делаем уровней? Для понимания условимся, что будем хранить $\log n$ уровней, однако утверждается, что если мы будем переходить на следующий уровень, пока туда хоть кто-то может перейти -- такая версия также будет быстро работать.

\Subsubsection{Find}

В принципе, можно идти втупую, но давайте лучше делать это умнее.\\
Предполагаем, что х есть в нашем Skip-List

\begin{code}
Find(x)
	v = LeftTop
    while (v->x != x)
    	if (v->r->x <= x)
        	v = v->r
        else
        	v = v->down
\end{code}

Мега объяснение почему это работает за $O(\log n)$. \\Интуитивное понимание: это очень похоже на бинарный поиск. \\Сколько раз мы можем перейти вниз? Понятно, что не более логарифма. Посчитаем матожидание от количества шашов на текущем уровне. Сколько раз мы можем перейти направо? Вероятность того, что на текущем уровне мы сделали не более одного шага -- $\frac{1}{2}$. Вероятность того, что на текущем уровне сделали не более двух шагов -- $\frac{1}{4}$ и так далее. Пусть мы сделали k шагов. Т.е. вероятность k-ого шага равна $\frac{1}{2^k}$. Тогда матожидание будет: $E = \sum \frac{k}{2^k}$. Как мы знаем из матана, этот ряд сходится и он равен $O(1)$. Значит, Find работает за $O(1)$. Теперь строже стало.

\Subsubsection{Add}

С помощью Find умеем найти место куда вставить x уже за $O(\log n)$. Вызовем его. Запомним позиции на каждом уровне такие, на которых Find был последний раз, т.е. прежде чем спуститься вниз. Т.е. $O(\log n)$ позиций. На самую нижнюю из них мы вставим $x$. На втором уровне вставим его с вероятностью $\frac{1}{2}$. Если мы вставили его на втором уровне, вставим его на третий уровень с вероятностью $\frac{1}{4}$. И так далее.

\Subsubsection{Delete}

Аналогично запускаем Find и выпиливаем нужный "столбец".

\Subsubsection{Split}

Через Find также находим столбец, обрубаем все связи на нем. Если в реализации предусмотрен фиктивный столбец слева(для удобства), добавляем его в получившуюся правую часть.

\Subsubsection{Merge}

Удаляем фиктивный столбец в правой части. Далее просто проводим ссылки.

\pagebreak
\vspace*{-1em}
\Subsection{Offline персистентность}

Вообще, далее на лекции были несколько задач и их разбор. Я напишу про 2 из них, если в будущем что-то еще появится в билетах, этот раздел дополнится.

Задача: даны запросы к СНМ вида, обратиться в $i$-ой версии и, например, объединить элементы $a$ и $b$, тем самым создав новую версию, или просто проверить, лежат ли $a$ и $b$ в одном множестве в $i$-ой версии СНМ. Это запросы первого и второго типа соответственно.

Решим в оффлайн за $O(n + m)$. ($n$ -- количество элементов в СНМ, $m$ -- количество запросов).

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

\pagebreak
\vspace*{-1em}
\Subsection{Persistent RBST}
\begin{Def}
	RBST(Randomized Binary Search Tree) -- BST, в котором каждая вершина, может стать корень равновероятно $\Leftrightarrow$ наша версия без $y$, а именно $y$-ки использовались в merge, теперь там строчка : $p = \frac{L.size()}{L.size() + R.size()}$. С вероятностью $p$, корнем merge будет корень левого поддерева, иначе будет корень правого поддерева.
\end{Def}
Мы хотим сделать его персистентным, будем каждый раз создавать новое дерево при любом изменении. Однако, если $А$ -- дерево, то merge$(A,A)$, выдаст дерево, по определению не являющимся RBST. 

\vspace*{0.5em}
\includegraphics[scale=0.11]{shavkunov/1.jpg}
\vspace*{0.5em}

Пусть 4 в правом дереве $А$, будет корнем результирующего дерева(фиксируем ее), тогда элементы левого дерева $А$ и левого поддерева 4, окажутся в левом поддереве результирующего дерева. По определению, вершина левого поддерева должна выбираться равновероятно. Смотрим, на левое поддерево 4. Каждая вершина выбирается с вероятностью $\frac{1}{3}$, т.к. это корректное произвольное BST. Значит при выборе корня в левом поддереве, каждая вершина из этого поддерева возьмется с вероятностью равно $\frac{3}{8} \cdot \frac{1}{3} = \frac{1}{8}$. Значит, с этим поддеревом все понятно. Теперь посмотрим на левое поддерево $А$. Здесь должно было бы получиться аналогично: каждая вершина должна была бы выбираться с вероятностью $\frac{1}{8}$, но на самом деле корнем будет 4 в левом дерева $А$. Всегда. Поскольку мы зафиксировали 4 в правом дереве и эта 4 всегда будет отцом, потому что деревья одинаковые. Т.е. 4 возьмется с вероятностью 1, а все остальные вершины будут с вероятностью 0. Т.е. получили, что по нашему определению, это не будет произвольным RBST. Однако утверждается, что при таком merge мы все равно получим RBST(без док-ва).
