42
правки
Изменения
Новая страница: «==Описание== Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализ…»
==Описание==
Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом.
==Алгоритм==
[[Файл:Down-up.png|right|350px|thumb|Реализация запроса снизу вверх]]
Будем рассматривать дерево отрезков с операцией нахождения минимального значения на отрезке(RMQ).<br>
Если левая граница является правым сыном, то отрезаем ее и аналогично рассматриваем правую границу (является ли правая граница левым сыном). Затем поднимаемся к родителям новых границ. Отрезая, мы считаем минимум из отрезанного значения и оставшегося отрезка.
==Псевдокод==
Псевдокод функции нахождения минимума на отрезке <tex>[left, right]</tex>.
segmentMin(left, right)
res = MAX_INT;
while left < right
if left == <правый сын>
res = min(result, data[left]);
left = <родитель правого соседа>;
else
left = <родитель left'a>;
if right == <левый сын>
result = min(result, data[right]);
right = <родитель левого соседа>;
else
right = <родитель right'a>;
if left == right
result = min(result, data[left]);
return result;
Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом.
==Алгоритм==
[[Файл:Down-up.png|right|350px|thumb|Реализация запроса снизу вверх]]
Будем рассматривать дерево отрезков с операцией нахождения минимального значения на отрезке(RMQ).<br>
Если левая граница является правым сыном, то отрезаем ее и аналогично рассматриваем правую границу (является ли правая граница левым сыном). Затем поднимаемся к родителям новых границ. Отрезая, мы считаем минимум из отрезанного значения и оставшегося отрезка.
==Псевдокод==
Псевдокод функции нахождения минимума на отрезке <tex>[left, right]</tex>.
segmentMin(left, right)
res = MAX_INT;
while left < right
if left == <правый сын>
res = min(result, data[left]);
left = <родитель правого соседа>;
else
left = <родитель left'a>;
if right == <левый сын>
result = min(result, data[right]);
right = <родитель левого соседа>;
else
right = <родитель right'a>;
if left == right
result = min(result, data[left]);
return result;
