добавлено: 24 Aug 2008 11:26
редактировано: 9 Sep 2008 15:52

Задача RMQ (Range Minimum Query - минимум на отрезке). Решение за O (1) с препроцессингом O (N)

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

Здесь описано асимтпотически оптимальное решение. Оно несколько стоит особняком от других алгоритмов решения RMQ, поскольку оно сильно отличается от них: оно сводит задачу RMQ к задаче LCA, а затем используеталгоритм Фарах-Колтона и Бендера, который сводит задачу LCA обратно к RMQ (но уже частного вида) и решает её.

Алгоритм

Построим по массиву A декартово дерево, где у каждой вершины ключом будет позиция i, а приоритетом - само число A[i] (предполагается, что в декартовом дереве приоритеты упорядочены от меньшего в корне к большим). Такое дерево можно построить за O (N). Тогда запрос RMQ(l,r) эквивалентен запросу LCA(l',r'), где l' - вершина, соответствующая элементу A[l], r' - соответствующая A[r]. Действительно, LCA найдёт вершину, которая по ключу находится между l' и r', т.е. по позиции в массиве A будет между l и r, и при этом вершину, наиболее близкую к корню, т.е. с наименьшим приоритетом, т.е. наименьшим значением.

Задачу LCA мы можем решать за O (1) с препроцессингом O (N) с помощьюалгоритма Фарах-Колтона и Бендера, который, что интересно, сводит задачу LCA обратно к задаче RMQ, но уже частного вида.