Изменения

Рассмотрим данную рекурсиюданный алгоритм на определенных глубинах рекурсии:

*Текущий полуинтервал <tex>[0 .. 8)</tex>, он больше пересекается с <tex>[1 .. 5) \Rightarrow</tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex>

*<tex>[0 .. 4)</tex> выходит за границы<tex> [1 .. 5)</tex>, и <tex>[4 .. 8)</tex> выходит за границы пересекаются с <tex>[1 .. 5) \Rightarrow </tex> , то переходим по рекурсивным вызовам на полуинтервалах <tex>[0 .. 2)</tex>, <tex>[2 .. 4)</tex> и , <tex>[4 .. 6)</tex>, и <tex>[6 .. 8)</tex>.

*<tex>[0 .. 2)</tex> выходит за границы и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1 , 4, 5 </tex>; <tex>[2 .. 4)</tex> целиком полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем значение в <tex>[2 .. 4)</tex>сумму на этом отрезке; а <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение; <tex>[4 .. 6)</tex> выходит за границы <tex>[1 .. 5) \Rightarrow </tex> переходим к листьям <tex>4</tex> и <tex>5</tex>.

*листья Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>5\Rightarrow </tex> и возвращаем значения в них, в то время как листья <tex>0, 5</tex> не пересекается с полуинтервалом лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение. Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, а листья отвечающих за полуинтервалы <tex>4[1 .. 2)</tex> и , <tex>1[2 .. 4)</tex> целиков внутри и <tex>[1 4 .. 5) \Rightarrow </tex> возвращаем значения в этих листьях.