I have $N$ uniformly distributed 2D points and I want to find out how many points lie in some small rectangular region. However, the number of points can be arbitrarily large (e.g., $N=10^8$), so I don't want to explicitly generate points and insert them in some spatial data structure. I am not interested in the actual locations of points, just the number of them in some region. The search region is not known in advance, and I can perform queries in many different regions.
One solution is to use a quadtree and for every region query you traverse the tree and generate the number of points inside a node using multinomial distribution with probabilities 1/4 each.
For example, at the top level of the tree (level 1), there are N points. After one subdivision, nodes have $N_1$, $N_2$, $N_3$ and $N_4$ points that were distributed with multinomial distribution. The number of points in four children nodes must sum to the number of points in the parent node: $N = N_1 + N_2 + N_3 + N_4$. We continue traversal to some arbitrary depth level until we account for all quadtree nodes that overlapped the query region. This approach works, but the performance bottleneck is repeated generation of the number of particles in each node being traversed.
Question: Is there a way to compute the number of points in a region using purely probabilistic approach?
If there is a consistent enumeration of nodes in a quadtree, is there an algorithm that allows me to make a query "how many points lie in a quadtree node X at level L?" without explicit generation of the tree or hierarchical traversal described above?