Изменения

Перейти к: навигация, поиск

Решение RMQ с помощью разреженной таблицы

30 байт добавлено, 09:53, 29 января 2019
м
Идемпотентность: Исправил ошибку
{{Утверждение
|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})$ содержится в обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
}}
2
правки

Навигация