Изменения

Таким образом, мы может можем ''нормализовать'' блок, вычтя из всех его элементов первый. Тем самым мы значительно уменьшим число возможных типов блоков.

Осталось создать <tex>O(\sqrt N)</tex> таблиц — по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросыминимума внутри блока соответствующего типа, коих <tex>(\frac{\log_2 N}{2})^2 = O(\log^2 N)</tex>. Для каждого блока в <tex>b_i</tex> необходимо заранее вычислить его тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за <tex>O(1)</tex>, затратив на предподсчёт <tex>O(\sqrt N \log^2 N)</tex> времени. Для каждого блока в <tex>b_i</tex> необходимо заранее вычислить его тип.