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)
