如果我有大量的连续范围(例如[0..5]，[10..20]，[7..13]，[-1..37])，并且可以将这些集合安排到任何数据结构中我喜欢，最有效的测试设置特定test_number所属的方法是什么？
我曾考虑过根据集合的低位数将集合存储在平衡的二叉树中(每个节点将拥有所有集合中具有相同最低数目的集合)。这将使您能够根据要针对集合进行测试的test_number是否小于集合的最低数目来有效地修剪集合的数量，然后修剪该节点以及该节点右边的所有节点(在其范围内具有一个较低的数字，该数字大于test_number)。我认为这将平均减少约25％的集合，但随后我需要线性查看二进制树中的所有其余节点，以确定test_number是否属于那些集合。 (我可以通过按集合中的最高编号对任意一个节点处的集合列表进行排序来进一步优化，这将使我能够在特定列表中进行二进制搜索，以确定哪个集合(如果有的话)包含test_number。不幸的是，大多数我要处理的集合中没有重叠的集合边界。)
我认为这个问题已经在图形处理中解决了，因为他们已经找到了有效测试整个模型中哪些多边形对特定像素起作用的方法，但是我不知道这种算法的术语。
最佳答案
您对问题与图形的相关性的直觉是正确的。考虑构建和查询segment tree。它非常适合您想要的计数查询。另请参见其description in Computational Geometry。