333
правки
Изменения
→Пример
* На глубине 1. <tex>[0 .. 4)</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>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение.
* На глубине 3.
** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них
** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение.
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.
