I am trying to solve a problem which involves a giant 2-D screen (40000 \* 40000 points) . There are some invalid points, and I have been given a rectangular window . All the points to the top-left of invalid points which fit within the rectangular window are invalidated as well.

I need to build a data structure which would support operations such as :
1) Find how many valid points i have to work on.
2) Query if a certain point is valid or not.

Based on my research, I have considered segment/interval trees, but I can't understand them fully, plus not sure if they can handle 2-D points.

Could anyone give me some nice article/implementation with a detailed description of a data structure which would enable above operations?

Thanks,
Rohit