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