Изменения

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

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

352 байта добавлено, 20:10, 31 марта 2012
Разреженная таблица
\right.
</tex> .
Это === Идемпотентность ===Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как идемпотентность она позволяет нам корректно считать минимум в области пересечения отрезков.  Таким образом мы получаем целый класс задач, которые могут решаться разреженной таблицей: вместо минимума может быть любая идемпотентноя бинарная операция <tex> f(x, x) = x </tex>.
== Применение к задаче RMQ ==
355
правок

Навигация