Изменения

<div> Предпосчитаем для длины отрезка <tex>l</tex> величину <tex>k j =\lfloor \log_2l \rfloor</tex>. Это можно сделать за <tex>O(N\log N)</tex> введением функции Для этого введем функцию <tex>fl[l] = kj</tex>, для которой верно <tex>fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1</tex>. Вычисление <tex>fl[l]</tex> происходит за <tex>O(\log (l))</tex>. А, так как длина может принимать <tex>N</tex> различных значений, то суммарное время предпосчета составляет <tex>O(N\log N)</tex>.

Пусть теперь дан запрос <tex>(l, r)</tex>. Заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][kj], ST[r-2^kj+1][j]\right)</tex>, где <tex>k j = \max \{jk| 2^j k \le r - l + 1\}</tex>, т.е. то есть логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за <tex>O (1)</tex>.

Стоит отметитьИз выше доказанной теоремы следует, что этот метод работает не только с операцией минимум, но и с любой идемпотентной, ассоциативной и коммутативной операцией, так как отрезки <tex>(l, 2^k)</tex> и <tex>(r - 2^k, r)</tex>, на которых мы считаем ответ, есть те самые из доказанного утверждения. Таким образом мы получаем целый класс задач, решаемых разреженной таблицей.