Изменения
→Алгоритм
== Алгоритм ==
Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы (sparse table, ST)]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>A_i</tex> на блоки длины <tex>\dfrac{1}{2}\log_2 N</tex>. Для каждого блока вычислим минимум на нём и определим <tex>B_i</tex> как позицию минимального элемента в <tex>i</tex>-ом блоке.
