42
правки
Изменения
→Алгоритм
[[Файл:Down-up1.png|right|350px|thumb|Реализация запроса снизу вверх]]
Будем рассматривать дерево отрезков с операцией нахождения минимального значения на отрезке(RMQ).<br>
Установим границы отрезка на соответствующие листья. Если левая граница элемент попавший на левую границу является правым сыном, то отрезаем ее и аналогично рассматриваем элемент попавший на правую границу (является ли правая граница левым сыном). Затем поднимаемся к родителям новых границ. Отрезая границу, мы считаем минимум из отрезанного значения и минимума на оставшемся отрезке.Закончим алгоритм, когда границы пересекутся.
==Псевдокод==
Псевдокод функции нахождения минимума на отрезке <tex>[left, right]</tex>.
