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