}}
== В чём профит? ==
Как и [[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | range tree]], данная структура умеет выдавать точки, принадлежащие какому-то прямоугольнику, алгоритм очень похож на тот, который применяется в range tree. Только ответ на запрос происходит за <tex>O(\log n + k)</tex> (вроде бы независимо от размерности, хотя квадродерево подразумевает двумерное пространство, но для обобщения на больше размерности асимптотика будет та же, кажется). И памяти нужно <tex>O(n)</tex>. Этим skip quadtree круче.
=== Как отвечать на запрос ===
Сначала локализуем все четыре точки прямоугольника
''Я тут понял, что пока не знаю, как это делать, сейчас буду думать.''
''Всё очень плохо, я тупой, меня можно побить.''
''Боря тоже не знает, так что я не тупой, меня не надо бить. А ещё выяснилось, что от нас это не требуется, так что особо любознательные могут сами подумать, а остальные могут просто забить.
== Источник ==
