Preprocess data such that locations within a rectangle drawn on a map can be found in less than O(n) time I came across this problem online and found no solutions or insight. The problem is stated as:


  Given a map as a square, and a set of locations on the map, users are able to select a rectangle on the map and all of the locations on the map are returned
  How would you preprocess the map data so that the find operation for the locations in the inner rectangle can be done in less than O(n) time?


I'm really stumped on this as the only thing I could think of is to create a hashmap that contains every single possible rectangle within the map with values that are lists of locations within said rectangle. However, it would not be practically feasible to store that much data.

Any help would be appreciated!
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!