Fast query on the number of elements in a quarter plane


I have a scatter of 2D elements on a 2D plane.

I would like an efficient algorithm to prepare and query the number of points in a quarter plane (inclusive of boundary).

The quarter plane is defined by a point $ (x,y)$ . All elements $ (x’, y’)$ where $ x<=x’$ and $ y<=y’$ are in the quarter plane.

For example

  • I have elements [(1,1), (2,2), (1,2), (3,2)],
  • My queries are [(1,1), (2,2), (3,3)]

The program should return [1,3,4].

This is for a past competitive programming challenge (WiFi Network problem in this competition)