Задача RMQ (Range Minimum Query - минимум на отрезке)

Дан массив A[1..N]. Поступают запросы вида (L, R), на каждый запрос требуется найти минимум в массиве A, начиная с позиции L и заканчивая позицией R.

Приложения

Помимо непосредственного применения в самых разных задачах, можно отметить следующие:

Задача LCA (наименьший общий предок)

Решение

Задача RMQ решается с помощью структур данных.

Из описанных на сайте структур данных можно выбрать:

Sqrt-декомпозиция - отвечает на запрос за O (sqrt (N)), препроцессинг за O (N).
Преимущество в том, что это очень простая структура данных. Недостаток - асимптотика.
Дерево отрезков - отвечает на запрос за O (log N), препроцессинг за O (N).
Преимущество - хорошая асимптотика. Недостаток - бОльший объём кода по сравнению с другими структурами данных.
Дерево Фенвика - отвечает на запрос за O (log N), препроцессинг за O (N log N)
Преимущество - очень быстро пишется и работает тоже очень быстро. Но значительный недостаток - дерево Фенвика может отвечать только на запросы с L = 1, что для многих приложений неприменимо.

Примечание. "Препроцессинг" - это предварительная обработка массива A, фактически это построение структуры данных для данного массива.

Теперь предположим, что массив A может изменяться в процессе работы (т.е. также будут поступать запросы об изменении значения в некотором отрезке [L;R]). Тогда полученную задачу можно решить с помощью Sqrt-декомпозиции и Дерева отрезков.