Sparse table

Задача RMQ.

---

Формулировка проблемы.
Есть массив, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами от L до R (не включая R)".

Идея решения
Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i e [0, n), k e [0, log n]. Таким образом, у нас O(n lon n) чисел. Шаг 0.
При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив.
...
Шаг k.
Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) U [I + 2^(k-1), i + 2^k). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).
В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.