Изменения
Нет описания правки
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>A_i</tex> на блоки длины <tex>\frac{1}{2}\log_2 N</tex>. Для каждого блока вычислим минимум на нём и определим <tex>B_i</tex> как позицию минимального элемента в <tex>i</tex>-ом блоке.
На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос <tex>RMQ</tex><tex>[i:j]</tex>, если <tex>i</tex> и <tex>j</tex> находятся в разных блоках, нам необходимо вычислить следующее:
=== Псевдокод ===
<code>
precalc(A : '''int[]''', N : '''int''')
block_size = log(N) / 2 <font color=green> // размеры блоков </font>
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> <font color=green> // количество блоков </font>
<font color=green>// предподсчитаем позиции минимумов в каждом блоке</font>
cur_block = 1
'''for''' i = 1 '''to''' K
B[i] = -1
'''for''' i = 1 '''to''' N
'''if''' j > block_size
j = 1
cur++
'''if''' B[cur] = -1 '''or''' A[B[cur]] > A[i]
B[cur] = i
</code>
=== Результат ===
