Изменения

Будем решать задачу RMQ, уже умея решать задачу LCA, для . Для хранения решения задачи о LCA будем использовать [[декартово дерево по неявному ключу]]. Тогда минимум на отрезке от <tex> i </tex> до <tex> j </tex> будет равен наименьшему общему предку <tex>i</tex>-того и <tex>j</tex>-того элементов из декартова дерева.