Preprocess data such that locations within a rectangle drawn on a map can be found in less than O(n) time
You should look into R-Trees.


  R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.


The parts that apply the most to your case are the ones described on the Search subsection. This operation on this kind of trees have a complexity of   O(logMn):


  In range searching, the input is a search rectangle (Query box). [...] the elements are tested against the search rectangle and their objects (if there are any) are put into the result set if they lie within the search rectangle.


Good luck!