Изменения

Перейти к: навигация, поиск
Пример
* На глубине 2. ** <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>.
333
правки

Навигация