24
правки
Изменения
м
Правка орфографии
Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \leqslant N </tex>.
Простой метод построения таблицы заключён в следующем реккурентном рекуррентном соотношении:
$$
ST[i][j]=
{{Утверждение
|statement=
$a_l \circ a_{l+1} \circ \ldots \circ a_r = (a_l \circ a_{l+1} \circ \ldots \circ a_ka_{l + k}) \circ (a_{r - k} \circ a_{r - k + 1} \circ \ldots \circ a_r)$, где $\frac{r - l }{2} \leqslant k \leqslant r- l$.
|proof=
Отрезок $(a_{r-k}, a_ka_{l + k})$ содержится в обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
}}
