我正在尝试解决一个涉及巨大二维屏幕(40000 * 40000 点)的问题。有一些无效点，给了我一个矩形窗口。所有位于矩形窗口内的无效点左上角的点也都无效。
我需要构建一个支持以下操作的数据结构: 1)找到我必须处理的有效点数。 2) 查询某个点是否有效。
根据我的研究，我考虑过线段/区间树，但我不能完全理解它们，而且不确定它们是否可以处理二维点。
任何人都可以给我一些不错的文章/实现，并详细描述可以实现上述操作的数据结构吗？
谢谢， 罗希特
最佳答案
这是今年facebook hackercup的“坏点”问题。请参阅official solution带有代码和解释。
关于algorithm - 存储二维区间的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14839255/