Изменения

|proof=Соседние элементы в блоках отличаются на <tex>\pm 1</tex>. Первый элемент в нормализованном блоке всегда равен нулю. Таким образом, каждый нормализованный блок может быть представлен <tex>\pm 1</tex>-вектором длины <tex> \bigg(\dfrac{1}{2} \log_2 N\bigg) - 1</tex>. Таких векторов <tex>2^{(\frac{1}{2} \log_2 N) - 1} = O(\sqrt N)</tex>.

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