Изменения
→Алгоритм
На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. При этом размер разреженной таблицы и время её построения будут равны:
<tex>\fracdfrac{N}{K}</tex><tex> log \fracdfrac{N}{K}=\bigg(\fracdfrac{2N}{log N}\bigg) log\bigg(\fracdfrac{2N}{log N}\bigg)=\bigg(\fracdfrac{2N}{log N}\bigg) \bigg(1 + log \bigg(\fracdfrac{N}{log N}\bigg)\bigg) \leqslant \fracdfrac{2N}{log N} + 2N </tex><tex>= O (N)</tex>
Теперь для ответа на запрос <tex>\mathrm{RMQ}</tex><tex>[l:r]</tex>, если <tex>l</tex> и <tex>r</tex> находятся в разных блоках, нам необходимо вычислить следующее:
