Изменения

Основная идея заключается в том, чтобы предподсчитать ответы для отрезков, длины которых являются степенями двойки. То есть <tex>M_i^k = min\{a_i, .., a_{i+2^k}\}</tex> — минимум на отрезке длины <tex>2^k</tex>, начинающемся в позиции <tex>i</tex>. Таким образом, таблица <tex>M</tex> имеет размер <tex>O(N logN)</tex>. Заполнить эту таблицу можно за <tex>O(N logN)</tex>дщинамически, если заметить, что <tex>M_i^0 = a_i</tex> и <tex>M_i^k = min\{M_i^{k-1}, M_{i+2^{k-1}}^{k-1}\}</tex> ''(см. картинку)''.

Пусть теперь необходимо вычислить минимум на отрезке <tex>[i:j]</tex>. Для этого мы покроем этот отрезок двумя отрезками длины <tex>2^k</tex> (где <tex>k = \lfloor log_2(j-i) \rfloor</tex>) так, чтобы первый отрезок начинался в <tex>i</tex>, а второй заканчивался в <tex>j - 1</tex>. Отрезки, разумеется, будут пересекаться, то это никак не помешает. В этом случае искомый минимум можно найти за константное время как минимум на этих двух блокахпокрывающих отрезках, т.е. <tex>min([i:j]) = min\{M_i^k, M_{j-2^k}^k\}</tex>.