Data structure in python for 2d range counting queries

I need a data structure for doing 2d range counting queries (i.e. how many points are in a given rectangle).

I think my best bet is range tree (it can count in log^2, or even log after some optimizations). Does it sound like a good choice? Does anybody know about开发者_JS百科 a python implementation or will I have to write one myself?

See scipy.spatial.KDTree for one implementation.

There's also a less generic (but occasionally more useful, particularly with regards to what you have in mind) implementation using shapelib's quadtree. See this blog and the corresponding package in PyPi.

There are probably other implementations, too, but those are the two that I've used...