E049. Problème RMQ (Range Minimum Query - минимум на отрезке). Solution за O (1) с препроцессингом O (N)

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

Дан tableau A[1..N]. Поступают запросы вида (L, R), на каждый запрос it is required find минимум в tableauе A, начиная с позиции L и заканчивая позицией R. tableau A изменяться в процессе работы не может, т.е. здесь описано Solution статической задачи RMQ. Здесь описано асимтпотически оптимальное Solution. Оно несколько стоит особняком от других Algorithmeов решения RMQ, поскольку оно сильно отличается от них: оно сводит задачу RMQ к задаче LCA, а затем использует Algorithme Фарах-Колтона и Бендера, который сводит задачу LCA обратно к RMQ (но уже частного вида) и решает её.

Algorithme

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