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

Алгоритм Фарака-Колтона и Бендера помогает решить задачу $RMQ \pm 1$ за время $O(n + q)$. Он не применим на практике, потому что имеет большую константу, но зато имеет важное теоритическое значение.

Сведение $RMQ \rightarrow RMQ \pm 1$

Во-первых, в статье про LCA рассказано, что $lca \rightarrow RMQ \pm 1$ через эйлеров обход (потому что разница высот соседних вершин ровно единица.

Во-вторых, по массиву $a_i$ можно за $O(n)$ построить декартово дерево с координатами $(i, a_i)$ с помощью стека. Тогда RMQ - это запрос LCA к нашему дереву.

Алгоритм

Давайте разобьем массив на блоки размером $\frac{\log_2n}{2}$. Зная минимум в блоке, построим на блоках Sparse Table за $O(\frac{2n}{\log_2n} \cdot \log \frac{2n}{\log_2n}) \le O(n)$. Теперь любой запрос разбивается на $O(1)$ запросов для блока и $O(1)$ запросов к Sparse Table, и нам осталось научиться выполнять запросы для блока. Для блока мы воспользуемся тем, что различных блоков мало. В самом деле, поскольку массив имел вид $a_i = a_{i - 1} \pm 1$, то для ответа на запрос в блоке нам нужно знать только первое значение в блоке и массив баланса. Для каждого типа блока мы предпосчитаем балансы для всех его подотрезков, суммарно за $O(2^{\frac{\log_2n}{2}} \cdot \log^2) = O(\sqrt n \cdot \log^2)< O(n)$.

---

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s