E119. Задача RMQ (Range Minimum Query - минимум на отрезке)

Task

Источник: e-maxx.ru/algo, страница PDF 393.

Дан массив A[1..N]. Поступают запросы вида (L, R), на каждый запрос требуется найти минимум в массиве A, начиная с позиции L и заканчивая позицией R.

Приложения

Помимо непосредственного применения в самых разных задачах, можно отметить следующие:

● Задача LCA (наименьший общий предок)

Решение

Задача RMQ решается с помощью структур данных. Из описанных на сайте структур данных можно выбрать:

● Sqrt-декомпозиция - отвечает на запрос за O (sqrt (N)), препроцессинг за O (N).

Преимущество в том, что это очень простая структура данных. Недостаток - асимптотика.

● Дерево отрезков - отвечает на запрос за O (log N), препроцессинг за O (N).

Преимущество - хорошая асимптотика. Недостаток - бОльший объём кода по сравнению с другими структурами данных.

● Дерево Фенвика - отвечает на запрос за O (log N), препроцессинг за O (N log N)

Преимущество - очень быстро пишется и работает тоже очень быстро. Но значительный недостаток - дерево Фенвика может отвечать только на запросы с L = 1, что для многих приложений неприменимо. Примечание. "Препроцессинг" - это предварительная обработка массива A, фактически это построение структуры данных для данного массива. Теперь предположим, что массив A может изменяться в процессе работы (т.е. также будут поступать запросы об изменении значения в некотором отрезке [L;R]). Тогда полученную задачу можно решить с помощью Sqrt-декомпозиции и Дерева отрезков.