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