355
правок
Изменения
→Постановка задачи RMQ
'''Разреженная таблица''' (англ. ''sparse table'') позволяет решать задачу online static RMQ за <tex>O(1)</tex> на запрос, с предподсчётом за <tex>O(N \log N)</tex> и использованием <tex>O(N \log N)</tex> памяти.
== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex> целых чисел. Поступают запросы вида <tex>(l, r)</tex>: , для каждого из которых требуется найти минимум среди элементов <tex>A[l], A[l + 1], \dots, A[r] </tex>.
== Разреженная таблица ==
