42
правки
Изменения
→Псевдокод
res = MAX_INT;
while left < right
if isRightSon(left == <правый сын>)
res = min(result, data[left]);
left = parent(left + 1);
else
left = parent(left);
if isLeftSon(right == <левый сын>)
result = min(result, data[right]);
right = parent(right - 1);
Функция <tex>parent()</tex> возвращает родителя аргумента.
Функции <tex>isLeftSon(), isRightSon()</tex> возвращают является ли элемент правым или левым сыном соответственно.
Пусть дерево отрезков реализовано на массиве с индексацией элементов с 1.
parent(vertex)
return vertex / 2;
isLeftSon(vertex)
if parent(vertex) * 2 + 1 == vertex
return true;
return false;
==Ссылки==
