我试图解决一个问题，涉及一个巨大的二维屏幕（40000*40000点）有一些无效点，我得到了一个矩形窗口矩形窗口中的无效点左上角的所有点也将失效。
我需要建立一个支持以下操作的数据结构：
1）找出我需要努力的有效点数。
2）查询某一点是否有效。
根据我的研究，我考虑过段/间隔树，但我不能完全理解它们，另外也不确定它们是否能处理二维点。
有谁能给我一些很好的文章/实现，其中详细描述了一个数据结构，将使上述操作？
谢谢，
罗希特
最佳答案
这是今年Facebook Hackercup的“死像素”问题。请参阅带有代码和说明的official solution。
关于algorithm - 存储2d间隔的数据结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14839255/