5 марта 2011 в 21:20

Задача RMQ — 1. Static RMQ из песочницы

Введение

Задача RMQ весьма часто встречается в спортивном и прикладном программировании. Удивительно, что на Хабре ещё никто не упомянул эту интересную тему. Попробую восполнить пробел.

Аббревиатура RMQ расшифровывается как Range Minimum (Maximum) Query – запрос минимума (максимума) на отрезке в массиве. Для определённости мы будем рассматривать операцию взятия минимума.

Пусть дан массив A[1..n]. Нам необходимо уметь отвечать на запрос вида «найти минимум на отрезке с i-ого элемента по j-ый».



Рассмотрим в качестве примера массив A = {3, 8, 6, 4, 2, 5, 9, 0, 7, 1}.
Например, минимум на отрезке со второго элемента по седьмой равен двум, то есть RMQ(2, 7) = 2.

В голову приходит очевидное решение: ответ на каждый запрос будем находить, просто пробегаясь по всем элементам массива, лежащим на нужном нам отрезке. Такое решение, однако, не является самым эффективным. Ведь в худшем случае нам придётся пробежаться по O(n) элементам, т.е. временная сложность этого алгоритма – O(n) на один запрос. Однако, задачу можно решить эффективнее.

дерево отрезков

интервальная модификация

двумерное дерево отрезков

смежная задача RSQ

дерево Фенвика

задача LCA

персистентная постановка задачи RMQ

…много чего интересного…

и самая прелесть: алгоритм Фараха-Колтона и Бендера и преобразование RMQ -> LCA -> RMQ±1, позволяющее решать задачу RMQ за (O(n), O(1))

За подробностями можно обращаться, например, в умную книжку Т. Кормена, Ч. Лейзерсона, и Р. Ривеста «Алгоритмы: построение и анализ».

В последующих темах будут появляться другие источники.

Благодарю за внимание.