355
правок
Изменения
→Идемпотентность
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
Таким образом мы получаем целый класс задач, которые могут решаться разреженной таблицей: вместо минимума может быть любая идемпотентноя бинарная операция <tex> f(x, x) = x , x \in X </tex>, где <tex>X</tex> {{---}} некое множество, над которым задан массив <tex>A</tex>.
== Применение к задаче RMQ ==
