Sparse Table

Алгоритм

Пусть дан массив из $n$ чисел, и требуется с предподсчётом за $O(n \log n)$ отвечать на запрос <<минимум на отрезке>> за $O(1)$ в онлайне.

Для этого сделаем следующий предподсчёт: в массиве для каждого подотрезка, длина которого является степенью 2, найдём минимум в нём. Таким обазом мы хотим найти минимум в отрезках $[0, 0],\ [1, 1],\ \ldots,\ [n-1, n - 1]$, $[0, 1],\ [1, 2],\ \ldots,\ [n - 2, n - 1]$, $[0, 3],\ [1, 4],\ \ldots,\ [n - 4, n - 1]$, и так далее.

Заметим, что сделать мы это можем за $O(n \log n)$. Заведём массив $S[n][\log n]$. Мы хотим, чтобы $S[i][j]$ было равно минимуму в отрезке, начиная с $i$ и имеющему длину $2^j$. Нетрудно заметить, что $S[i][0]$ равно числу, стоящему на $i$-м месте массива. Тепеь

Допишу потом