355
правок
Изменения
→Идемпотентность
=== Идемпотентность ===
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
<wikitex>
Пусть $\circ$ - произвольная бинарная операция, которая удовлетворяет свойствам:
* ассоциативности {{---}} $a \circ (b \circ c) = (a \circ b) \circ c $;
* коммутативности {{---}} $a \circ b = b \circ a$;
* идемпотентности {{---}} $a \circ a = a $.
{{Утверждение|statement=$a_l \circ a_{l+1} \circ \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant r$.|proof=Покажем, что $a \circ b \circ c \circ d = (a \circ b \circ c) \circ (b \circ c \circ d)$. Действительно, $a \circ b \circ c \circ b \circ c \circ d = a \circ b \circ b \circ c \circ c \circ d = a \circ b \circ c \circ d $. Будем применять это к выражению в правой части равенства до тех пор, пока не получим выражение в левой части. Поле каждого шага количество одинаковых элементов сократится на два. А так как их конечное четное число, то и количество шагов будет конечным.}}Таким образом мы получаем целый класс задач, которые могут решаться разреженной таблицей: вместо минимума может быть любая идемпотентноя бинарная операция <tex> f(x, x) = x, x \in X </tex>, где <tex>X</tex> {{---}} некое множество, над которым задан массив <tex>A.</texwikitex>.
== Применение к задаче RMQ ==
