Это дерево квадрантов (оно же kd-дерево) плохо работает для запроса "найди все точки"), если точки в нем лежат кучно и почти все попадают в ответ. В этом случае вы, как и в наивном решении, проверите почти все точки, но при этом потратите в несколько раз больше времени на накладные расходы - проверку пустых листов и обход дерева.
Еще, ваше дерево, если точки лежат кучно, создает очень много пустых вершин. Представьте, что все точки лежат очень близко к левому нижнему углу. Вы разобъете квадрат на 4 части, но 3 из них пусты. Вы повторяете эту операцию, пока квадраты не станут совсем маленькими и не разобьют точки на несколько групп.
Первая оптимизация - не добавлять точки по одной, а обрабатывать их группой. Если в текущей вершине точек слишком много - надо найти медианную точку по горизонтали, а внутри каждой группы медианную по вертикали. И будут у вас 4 прямоугольника на месте изначального, но они не будут выравнены как 4 четверти квадрата. Но зато будут всегда делить пополам.
Вторая оптимизация - если вы видите, что bounding rect текущей вершины лежит целиком в запросе - надо просто вернуть все точки.
Но есть другая структура, которая будет работать лучше в вашем примере, хоть и занимать в log n больше памяти.
Вам нужно
дерево отрезков бинарных деревьев поиска (можно использовать std::set).
Заведите дерево отрезков по OX, где каждая вершина будет упорядоченное по OY set всех точек попадающих в данный отрезок по X.
При запросе вы разбиваете отрезок по X запроса на Log n отрезков-вершин в дереве отрезков (это те вершыны, которые надо взять в запрос по ссылке выше) Далее в каждом из этих Logn сетов можно через lower_boundary и upper_boundary получить итераторы начала и конца всех точек в вашем запросе.
Т.е вы можете получить все точки за O(log n). Правда, какая-то обработка их уже будет O(n) в худшем случае - вся ассимптотика портиться. Но если вам нужно только их количество, то вы можете найти расстояния между двумя итераторами за константу и не надо точки никуда копировать в вектор.
Но даже если вам надо будет точки все в прямоугольнике обойти, то тут тоже можно ускорить немного - вы не копируйте точки в vector. Вы так и возвращайте вектор пар итераторв начала и конца в разных set-ах. И, если вам надо будет обойти точки - обходите двумя вложенными циклами - один по вектору пар итераторов, и второй по самим итераторам.
Еще, оптимизация, если у вас lower_bound оказался равен upper_bound, то не надо эту пару итераторов (пустой интервал) класть в массив ответа.
Еще один бонус этой структуры, что можно быстро удалять/добавлять/менять точки и все остается балансированным. Но, в отличии от kd-дерева, оно занимает в log n раз больше памяти и операция поиска всегда занимает O(log n + ответ), что может быть чуть медленее лучшего случая kd дерева, где вы можете сразу же закончить поиск, если очевидно, что в ответе ничего нет. Зато в худшем случае будет работать быстрее.
