\Section{RMQ и LCA}{15 марта}{Екатерина Кощенко}

\Subsection{RMQ offline.}

\t{RMQ.offline = RMQ $\to$ LCA + LCA.offline}

\vspace*{0.5em}
Решаем задачу на массиве $a[1..n]$

$m_0 = 0$

$m_{i+1} = \t{minpos}(m_i..n]$

$a[m_1] \le a[m_2] \le a[m_3] \le \dots$

Храним в СНМ множества $[1..m_1] (m_1..m_2] (m_2..m_3] \dots$.

СНМ поддерживает две операции: \t{get} и \t{join}.

Отсортируем все запросы по правой границе за линейное время.

Получили для каждой правой границы $R$ список левых концов $list[R]$.

Решение:

\begin{MyTabbing}
СНМ.init() \\
a[0] = ${-}\infty$\\
m.push\_back(0)\\
for R=1..n:\\
\>	for L $\in$ list[R]:\\
\>	\>	ответ для запроса (L,R) = min[СНМ.get(L)]\\
\>	while a[R] < a[m.back()]:\\
\>	\>	СНМ.join(m.back(), R), m.pop\_back() \\
\>	m.push\_back(R)
\end{MyTabbing}
При этом ``\t{min[корня множества]}'' пересчитывает \t{СНМ.join(a,b)}.

\Subsection{Сумма на пути дерева.}

Веса на ребрах меняются. Храним Эйлеров обход на ребрах, т.ч. при спуске к листьям записываем вес с плюсом, при подъеме ~--- с минусом. Для каждой вершины запомним, когда мы из нее вышли окончательно.\\
\verb'  'Как теперь с этим работать. Поменять вес на ребре = в ДО на обходе за логарифм поменять два элемента (проход вниз и вверх по ребру). Сумма на вертикальном пути = сумма на отрезке. Сумма на любом другом пути = разбиение на две суммы на вертикальных путях, точнее сумма на пути от A до LCA со знаком минус (ведь мы идем вверх, а не вниз по нему теперь), сложенная с суммой на пути от LCA до B. \\
\verb'  'Если веса не меняются, то проще будет ткая формула: $S(a, b) = S(a) + S(b) - 2S(LCA)$.

\pagebreak
\Subsection{Рандомизированный MST за линейное время.}

Пусть на очередном шаге алгоритма у нас n вершин и m ребер.\textit{Порядок действий:}
\begin{enumerate}
	\item Сделать 3 шага Борувки: $n->\frac{n}{8}$. Это делается за $\mathcal O(n + m)$.
	\item Берем рандомные $\frac{m}{2}$ ребер. Запускаем на них рекурсивный MST($\frac{n}{8}$, $\frac{m}{2}$). Этот MST вернет нам набор $A_{1}$ из не более чем $\frac{n}{8}-1$ ребер, которые он посчитает хорошими, то есть есть вероятность, что они могут попасть в наш остов. Набор $B_{1}$ оставшихся ребер плохой, в итоговом остове их точно не будет (это шло без доказательства).\\
	\item Переберем фориком оставшиеся $\frac{m}{2}$ ребер и проверим их. Если ребро может улучшить имеющийся сейчас остов, то есть оно меньше максимума на пути между двумя вершинами, что оно соединяет, то заменяем этот максимум на него и складываем ребро в множество $A_{2}$. Искать максимум на пути мы за единицу пока не умеем, но так можно. Изначально считаем, что граф полный и веса "отсутствующих" по факту ребер INF. Если же ребро никак улучшить ситуацию не может, то кидаем в $B_{2}$. Утверждение: ребра из $B_{2}$ в остов не входят.
	\item По итогам получаем два множества кандидатов в остов: $A_{2}$ и $A_{1}$. Запускаем рекурсивный $MST(\frac{n}{8}, |A_{1}|+|A_{2}|)$. Заметим, что резмер множества $A_{1}$ и матожидание размера $A_{2}$ не больше, чем $\frac{n}{8}-1$.
	\item Сколько же это работает? $T(n, m)\leq(n + m) + T(\frac{n}{8}, \frac{m}{2}) + T(\frac{n}{8}, \frac{n}{4})$. То есть вся эта прелесть работает за $\mathcal O(n + m)$.
\end{enumerate}
\begin{Lm}
Пусть p -- вероятность, с которой брали ребро на втором шаге (в описанном выше алгоритме это $\frac{1}{2}$). Тогда матожидание размера множества $A_{2}$ не больше, чем $(\frac{1}{p} - 1)(n - 1)$.
\end{Lm}
\begin{proof}
Представим себя Краскалом. Упорядочим ребра по весу, начинаем их перебирать. Если встречаем ребра, которое надо бы добавить в остов, то с вероятностью p добавляем, а с 1-p пропускаем. Рассмотрим первый такой момент, когда добавили ребро в остов. Посчитаем матожидание количества "бросков монетки" нужное для того, чтобы ребро добавилось. $E_{k} = 1+(1-p)\cdot E_{k}$. Отсюда $E_{k}=\frac{1}{p}$. Что в себя включает это $E_{k}$? Одно ребро из $A_{1}$ и $E_{k}-1=\frac{1}{p}-1$ ребер из $A_{2}$, они нас и интересуют.Это мы добавили одноребро в остов. Надо повторить процесс n-1 раз. Отсюда и матожидание $(\frac{1}{p} - 1)(n - 1)$.
\end{proof}
