Изменения
→Запрос точек в прямоугольнике
* <tex>\mathrm{stabbing}</tex> {{---}} пронзающие, пересекающие <tex>R</tex>, но не являющие внутренними (3, 4 и 5 на рисунке).
Для вершин из классов <tex>\mathrm{in}</tex> и <tex>\mathrm{out}</tex> ответ на запрос находится тривиально, {{---}} все поддерево вершины и никакие точки из поддерева соответственно; сложность представляют вершины из класса <tex>\mathrm{stabbing}</tex>. Зная их все, мы можем ответить на запрос.
Мощность множества пронзающих вершин может составлять <tex>O(n)</tex>, так как пронзающие вершины могут быть вложены друг в друга, тогда как нам достаточно рассмотреть только наименьшую из вложенных вершин.
