94
правки
Изменения
Нет описания правки
Min(left, right)
result = +inf; //Присваиваем результату максимально возможное значение
while (left < right) //Выполняем цикл до тех пор пока левая и правая граница не совпадут if ((left) / 2) * 2 == left // Проверяем является ли левая граница правым сыном result = min(result, data[left.data]); // Если является то пересчитаем результат и перенесем левую границу
left = (left + 1) / 2;
else
left = (left) / 2; // Если не является, то установим границу на родительский элемент текущей границы
if ((right) / 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей result = min(result, data[right.data]);
right = (right - 1) / 2;
else
right = (right) / 2;
if (left == right) // После окончания цикла проверяем совпали ли границы result = min(result, data[left.data]); // Если надо пересчитываем результат
return result;
[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]
[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия {{---}} Дерево отрезков — Википедия]
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]
