Запит мінімуму на відрізку (RMQ)

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

Запит мінімуму на відрізку (RMQ) може траплятися в задачах напряму або застосовуватися в інших задачах, наприклад у задачі про найнижчого спільного предка.

Розв'язок

Існує безліч можливих підходів і структур даних, які можна використати для розв'язання задачі RMQ.

Ті з них, що пояснені на цьому сайті, перелічені нижче.

Спершу підходи, які дозволяють змінювати масив між відповідями на запити.

• Кореневе розбиття — відповідає на кожен запит за $O(\sqrt{N})$, попередня обробка виконується за $O(N)$. Плюси: дуже проста структура даних. Мінуси: гірша складність.
• Дерево відрізків — відповідає на кожен запит за $O(\log N)$, попередня обробка виконується за $O(N)$. Плюси: добра часова складність. Мінуси: більший обсяг коду порівняно з іншими структурами даних.
• Дерево Фенвіка — відповідає на кожен запит за $O(\log N)$, попередня обробка виконується за $O(N \log N)$. Плюси: найкоротший код, добра часова складність. Мінуси: дерево Фенвіка можна використовувати лише для запитів з $L = 1$, тому воно не застосовне до багатьох задач.

А ось підходи, які працюють лише зі статичними масивами, тобто значення в масиві не можна змінити без перебудови всієї структури даних.

• Розріджена таблиця — відповідає на кожен запит за $O(1)$, попередня обробка виконується за $O(N \log N)$. Плюси: проста структура даних, чудова часова складність.
• Sqrt Tree — відповідає на запити за $O(1)$, попередня обробка виконується за $O(N \log \log N)$. Плюси: швидкий. Мінуси: складний у реалізації.
• Система неперетинних множин / трюк Arpa — відповідає на запити за $O(1)$, попередня обробка за $O(n)$. Плюси: короткий, швидкий. Мінуси: працює, лише якщо всі запити відомі заздалегідь, тобто підтримує лише офлайн-обробку запитів.
• Декартове дерево і алгоритм Фараха-Колтона та Бендера — відповідають на запити за $O(1)$, попередня обробка за $O(n)$. Плюси: оптимальна складність. Мінуси: великий обсяг коду.

Зауваження: попередня обробка — це попереднє опрацювання заданого масиву шляхом побудови відповідної структури даних для нього.

Задачі для практики

• SPOJ: Range Minimum Query
• CODECHEF: Chef And Array
• Codeforces: Array Partition

Відеоматеріали