algorithm - 存储二维区间的数据结构

Question

我正在尝试解决一个涉及巨大二维屏幕(40000 * 40000 点)的问题。有一些无效点，给了我一个矩形窗口。所有位于矩形窗口内的无效点左上角的点也都无效。

我需要构建一个支持以下操作的数据结构:1)找到我必须处理的有效点数。2) 查询某个点是否有效。

根据我的研究，我考虑过线段/区间树，但我不能完全理解它们，而且不确定它们是否可以处理二维点。

任何人都可以给我一些不错的文章/实现，并详细描述可以实现上述操作的数据结构吗？

谢谢，罗希特

Answer 1

这是今年facebook hackercup的“坏点”问题。请参阅official solution带有代码和解释。