Sparse nlognlogn
Другие решения
Многим известен алгоритм Sparse table, который работает за O(n log n) на построение и O(1) и решает задачу static RMQ. Так же эту задачу решает алгоритм ФКБ за O(n) на построение и O(1) на запрос, но при этом имеет неприлично большую константу и неприятен в написании. В следствии чего ФКБ мало применим в олимпиадных задачах.
Идея 1
Построение
Разобьём массив, на котором мы будем отвечать на запросы на блоки по logn, в каждом из блоков построим обычный sparse table за O(lognloglogn) количество таких блоков = n/logn => суммарно эти построения будут выполнены за O(nloglogn). В каждом блоке посчитаем минимум и на этих минимумах построим также sparse за O((n/logn) * log(n / logn)) <= O(n).
Ответ на запрос
Заметим, что если левая(l) и правая(r) границы запроса полностью лежат в одном блоке, то мы можем ответить за O(1) за счёт насчитанного в блоке Sparse table, если же l и r в разных блоках то введем l1 = (l / logn) + 1, r1 = (r / logn) — 1. Очевидно что ответ будет минимум из минимума на суффиксе блока l и префиксе блока r, и минимума на вех блоках с номерами с [l1 : r1] => ответ на запрос происходит за O(1)
