Изменения

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

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

25 байт добавлено, 14:38, 7 мая 2012
Постановка задачи 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>.
== Разреженная таблица ==
Анонимный участник

Навигация