Изменения
Нет описания правки
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>A_i</tex> на блоки длины <tex>\frac{1}{2}\log_2 N</tex>. Для каждого блока вычислим минимум на нём и определим <tex>B_i</tex> как позицию минимального элемента в <tex>i</tex>-ом блоке.
=== Псевдокод ===
<code>
'''int''' interpolationSearch(a : '''int[]''', key : '''int''') <font color=green> // a должен быть отсортирован </font>
left = 0 <font color=green> // левая граница поиска (будем считать, что элементы массива нумеруются с нуля) </font>
right = a.length - 1 <font color=green> // правая граница поиска </font>
'''while''' a[left] < key '''and''' key < a[right]
mid = left + (key - a[left]) * (right - left) / (a[right] - a[left]) <font color=green> // индекс элемента, с которым будем проводить сравнение </font>
'''if''' a[mid] < key
left = mid + 1
'''else if''' a[mid] > key
right = mid - 1
'''else'''
'''return''' mid
'''if''' a[left] == key
'''return''' left
'''else if''' a[right] == key
'''return''' right
'''else'''
'''return''' -1 <font color=green>// если такого элемента в массиве нет </font>
</code>
На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос <tex>RMQ</tex><tex>[i:j]</tex>, если <tex>i</tex> и <tex>j</tex> находятся в разных блоках, нам необходимо вычислить следующее:
Осталось создать <tex>O(\sqrt N)</tex> таблиц {{---}} по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, которых <tex>(\frac{1}{2}\log_2 N)^2 = O(\log^2 N)</tex>. Для каждого блока в <tex>B_i</tex> необходимо заранее вычислить его тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за <tex>O(1)</tex>, затратив на предподсчёт <tex>O(\sqrt N \log^2 N)</tex> времени.
=== Результат ===
