Изменения

Выше описан Следующий [[Декартово дерево#Построение декартова дерева|алгоритм построения дерева ]] строит декартово дерево за <tex>O(n)</tex>.Используя [[Сведение задачи LCA к задаче RMQ]], получаем:Препроцессинг препроцессинг для <tex>LCA</tex> {{---}} <tex>O(n)</tex> , и ответ на запрос {{---}} <tex>O(1)</tex>. В итоге получили <tex>RMQ</tex> {построение с построением за <tex>O(n)</tex>, и ответом на запрос за <tex>O(1)</tex>}.