!Static RMQ

Range minimum query - одна из базовых задач на массивах, она заключается в поиске минимума на любом подотрезке массива. Приписка Static означает, что в этой версии задачи изменений не происходит.

Sparse table

Используя разреженную таблицу мы решаем эту задачу за $O(n{\log }_{2}n)$ предподсчета и $O(1)$ на запрос.

Связь Static RMQ и LCA

Мы уже умеем решать задачу !Lowest common ancestor за $O(n)$ предподсчета и $O(1)$ на запрос с помощью алгоритма Фарака-Колтона-Бендера. Это решение можно обобщить на задачу Static RMQ, чтобы это сделать построим Декартово дерево, в котором ключами будут индексы массива, а приоритетами сами значения массива, оно получится несбалансированным, но это неважно. Теперь для получения ответа на отрезке $[l,r]$ мы просто ищем $LCA(l,r)$. Работает за $O(n)$ предподсчета и $O(1)$ на запрос.