Изменения

== Идемпотентность ==

Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.

Пусть $\circ$ — произвольная бинарная операция, которая удовлетворяет свойствам:

* ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c $,

Отрезок $(a_{r-k}, a_k)$ содержится в обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.

}}

== Применение к задаче RMQ ==