!Lowest common ancestor

Lowest common ancestor - одна из базовых задач на деревьях: для двух вершин дерева v и u мы хотим найти самого низкого общего предка для них.

Медленное решение

Как и в !LA мы будем идти от самого простого, медленного решения, к самому быстрому и сложному. В этой задаче самым простым будет просто высчитывание высот каждой вершины, а потом переход в предка из либо только более низкой вершины, либо из обеих вершин. Продолжаем алгоритм пока вершины не совпадут. Вершина, в которой мы окажемся, и будет LCA(u, v). Работает это чудо в худшем случае за $O(n)$ на бамбуке, если взять корневую вершину и лист.

Бинарные подъемы

Насчитаем те же подъемы, что и в LA. С помощью них за $O({\log }_{2}n)$, мы сначала поднимаем более низкую вершину на уровень второй. Теперь начнем перебирать все степени 2 по убыванию, и если при поднимании на них мы приходим в разные вершины, то мы поднимаемся, иначе нет.
Утверждение. После выполнения этого алгоритма, предком полученных вершин u и v будет одна и та же вершина, она и является LCA исходных вершин u и v.
Доказательство. Пусть при подъеме на x из u и v мы придем в $LCA(u,v)$, тогда рассмотрим $x-1$, он получается суммой различных степеней 2. Высота, на которую мы поднимемся при работе алгоритма хотя бы $x-1$, ведь на всех уровнях ниже $LCA(u,v)$ предки u и v различаются по определению $LCA(u,v)$, также высота, на которую мы поднимемся при работе алгоритма не может быть больше чем $x-1$, ведь все предки u и v, которые находятся на уровне $LCA(u,v)$ или выше - совпадают. Общая сложность работы программы:

$$O({\log }_{2}n+{\log }_{2}n)=O({\log }_{2}n)$$

c предподсчетом $O(n{\log }_{2}n)$.

Разреженная таблица

С помощью обхода эйлера мы можем свести задачу с дерева на массив.
Утверждение. При таком обходе $LCA$ вершин u и v хотя бы раз встречается между любой парой этих вершин в обходе, и при этом имеет наименьший уровень среди таких вершин.
Доказательство. Пусть первой в посещении будет вершина u. Тогда последний раз, когда она будет записана, это при выходе из нее в предка. После этого мы когда-то попадем в v, а значит пройдемся по пути из u в v, и будут записаны все вершины на пути, в которые $LCA(u,v)$ входит. Про наименьшую высоту проще, первый раз мы зашли $LCA(u,v)$ до захода в u, а выйдем после выхода из v, а все посещенные вершины после захода в любую вершину x и до выхода из нее имеют высоту, большую чем x. Тогда после выполненного обхода вся задача сводится к static RMQ, мы делаем обход и получаем 2 массива: массив высот, а также сам массив обходов, а также записываем для каждой вершины номер какого-то ее вхождения в массив обхода. Теперь на массиве высот строим разреженную таблицу за $O(n{\log }_{2}n)$ и отвечаем на любой запрос за $O(1)$.

Код

Алгоритм Фарака-Колтона и Бендера

Как и в LA воспользуемся идеей корнячки. Пусть S = $\frac{{\log }_{2}n}{2}$. Поделим массив нашего обхода на блоки размера S и сделаем уже на их минимумах по высоте разреженную таблицу. Тогда эта таблица строиться за $O\left(\frac{2n}{{\log }_{2}n}{\log }_{2}n\right)=O(n)$. Теперь осталось разбирать маленькие случаи, не превышающие один блок. Для этого заметим, что у нас не обычная задача static RMQ, соседние значения массива различаются ровно на 1, этим можно воспользоваться, давайте представим маску в виде битовой последовательности. Тогда можно перебрать все маски и для каждой посчитать минимум по высоте. Это все будет работать за:

$$O\left(2^{\frac{{\log }_{2}n}{2}}\ast \frac{{\log }_{2}n}{2}\right)=O(\sqrt{n}{\log }_{2}n)$$

Теперь, разберемся что мы хотим получить, запрос может полностью лежать в одном блоке, а также часть запроса может быть в конце блока или в его начале, то есть нам нужны суффиксы и префиксы. Пусть в маске у нас 0 - спуск вниз, 1 - подъем. Тогда любой префикс длины k можно стереть, если сделать взятие по модулю $2^{S-k}$, что как раз заменит префикс размера k на спуски вниз и там не может быть ответа. С суффиксом можно сделать то же самое сначала сдвинем на k вправо, потом на k влево и добавим $2^k-1$, что равно замене суффикса k на подъемы вверх. Таким образом мы можем получить минимум по высоте на любой маске блока, просто поменяв ее. Получается предподсчет $O(n)$ и время работы $O(1)$.