Изменения

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

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

19 байт убрано, 14:25, 22 апреля 2012
small fix
Такая простота достигается за счет идемпотентности операции минимум: <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 $.
Анонимный участник

Навигация