74
правки
Изменения
м
Для нахождения минимума на отрезке будем использовать информацию Будем решать задачу RMQ, уже умея решать задачу LCA, для хранения решения задачи о наименьшем общем предке. Для хранения наименьших общих предков LCA будем использовать [[декартово дерево по неявному ключу]].
→Алгоритм
===Описание===
[[Файл:Wiki.PNG|thumb|right|300x150px|Пример декартового дерева]]
Декартово дерево по неявному ключу на массиве <tex>A[1..N]</tex> {{---}} это бинарное дерево, допускающее следующее рекурсивное построение:
