Изменения
→Сложность: small innocent inconsiderable fixup
== Сложность ==
Следующий [[Декартово дерево#Построение декартова дерева|алгоритм]] строит декартово дерево за <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>.
