\Section{Фарах-Колтон и Бендер}{2 марта}{Севастюк Дмитрий}

\Subsection{Что уже есть}

Мы умеем решать задачу поиска минимума на отрезке (RMQ) с помощью дерева оторезков и получать следующую ассимптотику:

\begin{MyList}
	\item \t{init} -- построение, $\O(n)$
	\item \t{get(L, R)} -- минимум на отрезке [L, R], $\O(\log n)$
	\item \t{change(i, X)} -- изменить i-й элемент массива на X, $\O(\log n)$
\end{MyList}

\begin{Thm}{\emph{Lower Bound}}\\
	Нельзя сделать get, change за $o(\log n)$.
\end{Thm}
\begin{proof} 
	Пусть можно. Тогда мы получили сортировку за $o(n \log n)$.
\end{proof}

\Subsection{Sparse Table}

Это структура данных, умеющая init за $\O(n \log n)$ и get за $\O(1)$, но не умеющая change.\\
Пусть был исходный массив $a$. Тогда от каждой точки $i$ для каждой длины $2^k$ будем хранить минимум $m[k, i]$. Посчитать его можно динамикой:

\begin{equation*}
\begin{cases}
m[0, i] = a[i] \\
m[k, i] = min(m[k-1, i], m[k-1, i + 2^{k - 1}])
\end{cases}
\end{equation*}

get будет покрывать [L, R] двумя отрезками, для которых посчитаны минимумы. Для этого просто берётся максимальная не превосходящая R-L+1 степень двойки. Один отрезок такой длины начинается в точке L, второй отрезок такой длины заканчивается в точке R. Наименьший из минимумов на этих отрезках и есть минимум на [L, R].

get(L, R) = $min(m[k, L], m[k, R-2^k+1]) \text{, где предподсчитанное } k: 2^k \leq R - L + 1 < 2^{k + 1}$

\Subsubsection{Super Sparse}

Соединим Sparse Table с Деревом Отрезков, чтобы стало ещё быстрее. Две модификации:

\begin{MyList}
	\item init за $\O(n \log \log n)$, get за $\O(1)$
	\item init за $\O(n)$, get за $\O(\log \log n)$
\end{MyList}

В обоих случаях сначала разобьём исходный массив $a$ на кусочки длины $\log n$ и заведём массив $b$ -- минимумы на этих кусочках. Размер массива $b$ равен $k := \lceil n / \log n \rceil$. Теперь построим Sparse Table от $b$. Это займёт $\O(k \log k) = \O(n)$ времени. Осталось только научиться обрабатывать частичные префиксы/суффиксу -- расстояния от L/R до ближайшей внутренней границы кусочка (или от L до R, если между ними нет граници). Обозначим минимум на префиксах как $p[i]$ (аналогичный массив $s$ для суффиксов), где $i$ -- L или R соответственно.

\begin{equation*}
\begin{cases}
p[i] = +\infty \text{, если $i$ -- граница} \\
p[i] = min(a[i], p[i +  1]) \text{, если $i$ -- не граница}
\end{cases}
\end{equation*}

Если между L и R есть граница -- позвращаем $min(min \text{ из Sparse Table от } b, p[L], s[R])$.\\
Иначе нужно возвращать минимум напрямую на [L, R]. Для этого придётся заранее на каждом кусочке завести структуру данных, которая будет быстро выдавать минимум на [L, R], если тот оказался внутри этого кусочка. Это может быть либо Дерево Отрезков, влекущее get за $\O(\log \log n)$, либо Sparse Table, влекущее init за $\O(n \log \log n)$.

\Subsection{алгоритм Фараха-Колтона и Бендера}

\Subsubsection{Анонс}

Теперь научимся решать RMQ с init за $\O(n)$ и get за $\O(1)$. Для этого сведём RMQ к LCA (поиск наименьшего общего предка в подвешенном за корень дереве), а её -- к RMQ$\pm$1 (частный случай RMQ, в котором соседние числа отличаются ровно на 1). Каждое сведение будет за $\O(n)$ предподсчёта, а RMQ$\pm$1 уже научимся решать с init за $\O(n)$ и get за $\O(1)$.

Стоит упомянуть, что приведённая здесь версия на практике не лучше, чем Super Sparse через Дерево Отрезков. Однако существует более новая версия этого алгоритма, использующая $\O(n)$ бит памяти.

\Subsubsection{RMQ $\rightarrow$ LCA}

Вспомним Декартово Дерево (Cartesian Tree). Давайте построим его от нашего массива $a$. Пары <значение, ключ> (<$x$, $y$>) в дереве -- пары <$a[i]$, $i$>. Внезапно оказывается, что если составить массив пар, где $i$-я пара -- <$a[i]$, $i$>, то в нём элементы будут возрастать по ключу. Осталось только научиться строить Декартово Дерево от такого массива за $\O(n)$.

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

Для начала, в качестве корня выберем фиктивную минус бесконечность. Кладём её на стек. В дальнейшем будем подвешивать к ней. Пусть теперь мы хотим добавить новую вершину <$a[k]$, $k$>. Последовательно убираем вершины со стека (запоминая последнюю убранную), пока значение верхней из оставшихся на стеке больше, чем $a[k]$. Фактически, мы поднимаемся по дереву. При этом стек не окажется пуст, потому что фиктивный корень всегда меньше. Когда остановились -- удаляем ребро между верхней	на стеке вершиной и той, которую убрали последней. Заметим, что это ребро ``вправо''. На место этого ребра ``вклиниваем'' нашу новую вершину, то есть подвешиваем <$a[k]$, $k$> к верхней на стеке вершине как правого потомка и добавляем <$a[k]$, $k$> на стек, а потом, если есть последняя убранная со стека вершина, подаешиваем её к <$a[k]$, $k$> как левого потомка.

\begin{Lm}\label{Lm:lm31} 
	$\O(n)$.
\end{Lm}
\begin{proof} 
	Каждую вершину положили на стек 1 раз, а убрали -- не больше.
\end{proof}

\begin{Lm}\label{Lm:lm32} 
	Корректность дерева.
\end{Lm}
\begin{proof} 
	Старые элементы не поменяли свой порядок (левее/правее) друг относительно друга, а новый -- правее всех и больше всех по изначальному условию.
\end{proof}

\begin{Lm}\label{Lm:lm33} 
	Равносильность RMQ и LCA.
\end{Lm}
\begin{proof} 
	В получившемся дереве каждая вершина соответствует отрезку, причём корень соответствует всему массиву. При спуске от корня к L и к R последняя общая вершина -- последняя вершина, соответствующая отрезку, содержащему весь [L, R]. При этом значения соответствующих отрезкам вершин -- минимальные элементы исходного массива на этих отрезках. Значит, ответ на RMQ -- наименьший общий предок, то есть LCA.
\end{proof}

\Subsubsection{LCA $\rightarrow$ RMQ$\pm$1}

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

\begin{MyList}
	\item Последовательно сохранять номера всех посещённых вершин.
	\item Последовательно сохранять номера всех посещённых впервые вершин (просто dfs).
	\item Последовательно сохранять все посещённые ориентированные рёбра, предварительно разделив каждое неориентированное ребро на 2 ориентированных в разные стороны.
\end{MyList}

Второй способ интересен тем, что поддеревья в дереве являются отрезками в массиве обхода, то есть вершины любого поддерева расположены в массиве обхода без ``дырок'' из других вершин.

Но в данной задаче нам нужен первый способ. Если при обходе всегда поворачивать в самого левого из непосещённых потомка (если таковые есть), а вместо самих вершин сохранять их глубину ($height[v]$), то мы получим всё ещё однозначно задающий дерево массив, соответствующий ``условию $\pm$1'' -- разность соседних элементов равна 1.

\begin{Lm}\label{Lm:lm34} 
  RMQ$\pm$1 на Эйлеровом обходе через $height$ = LCA на исходном дереве.
\end{Lm}
\begin{proof} 
  Договоримся, что в запросе lca($v$, $u$) $v$ не правее $u$. Почему LCA на отрезке [$v$, $u$] в $height$? Потому что чтобы прийти из $v$ в $u$ нужно обязательно пройти через какого-то общего предка, а для этого нужно пройти через ближайшего общего предка. Почему неит других общих предков? Потому что при переходе в ближайшего общего предка по пути из $v$ алгоритм бы не поднялся, если бы не были проверены все дети, а значит и все потомки потомки LCA (в том числе и $u$), поэтому, если он вернулся в другого общего предка, то $u$ алгоритм уже посетил последний раз, из чего следует, что все остальные общие предки лежат вне отрезка [$v$, $u$]. Почему LCA -- минимум? Потому что алгоритм не поднимется выше LCA ни до него, ни после, ведь иначе LCA -- не общий предок.
  
  Проще говоря, это правда, потому что наш обход -- честный и порядочный dfs.
\end{proof}

\Subsubsection{RMQ$\pm$1}

?
