Изменения

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

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

118 байт убрано, 01:00, 16 апреля 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</tex>[l], начиная с позиции <tex>A[l</tex> и заканчивая позицией <tex>+ 1], \dots, A[r] </tex>.
== Разреженная таблица ==
355
правок

Навигация