228
правок
Изменения
Нет описания правки
==Пример==
[[Файл:Отрезки.JPG|right|380px|thumb|Дерево отрезков]]
Рассмотрим работу программы на дереве отрезков для элементов [1 .. 8].
Пусть запрашиваемая сумма - это отрезок [2 .. 5].
1)Текущий отрезок [1 .. 8], он больше [2 .. 5] => переходим по рекурсивным вызовам на [1 .. 4] и [5 .. 8]
2)[1 .. 4] выходит за границы [2 .. 5], [5 .. 8] выходит за границы [2 .. 5] => переходим по рекурсивным вызовам на [1 .. 2], [3 .. 4] и [5 .. 6], [7 .. 8].
3)[1 .. 2] выходит за границы [2 .. 5] => переходим в листья 1, 2; [3 .. 4] целиком внутри [2 .. 5] => возвращаем значение в [3 .. 4];
[7 .. 8] не пересекается с [2 .. 5] => возвращаем нулевое значение, [5 .. 6] выходит за границы [2 .. 5] => переходим к листьям 5 и 6
4)лист 6 не пересекается с отрезком [2 .. 5] => возвращаем нулевое значение, лист 5 целиков внутри [2 .. 5] => возвращаем значение в листе 5.
