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

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

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

Приложения

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

● Task LCA (Lowest common ancestor)

Solution

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

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

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

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

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

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

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