MAXimal | |
добавлено: 11 Jun 2008 11:02 Содержание [скрыть] Задача RMQ (Range Minimum Query - минимум на отрезке)Дан массив A[1..N]. Поступают запросы вида (L, R), на каждый запрос требуется найти минимум в массиве A, начиная с позиции L и заканчивая позицией R. ПриложенияПомимо непосредственного применения в самых разных задачах, можно отметить следующие: РешениеЗадача RMQ решается с помощью структур данных. Из описанных на сайте структур данных можно выбрать:
Примечание. "Препроцессинг" - это предварительная обработка массива A, фактически это построение структуры данных для данного массива. Теперь предположим, что массив A может изменяться в процессе работы (т.е. также будут поступать запросы об изменении значения в некотором отрезке [L;R]). Тогда полученную задачу можно решить с помощью Sqrt-декомпозиции и Дерева отрезков.
|