哪种数据结构最好检查值是否在定义块边界的a和b之间

Question

我有下表：

块_开始_结束。

1\x{e76f}1/2 2-5-9 3/ 10 / 20 4/ 21 / 50 . 编号: 1000 / 2000

当给定变量c的值时，我必须搜索哪个块包含c( start

Answer 1

如果整数的整个范围仅为1..2000，则可以将数据看作如下表：

n   block
1   1
2   1
3   1
4   0
5   0
6   2
.
.
.

它将实现为2000元素的向量。简单地查找向量中的元素n将告诉您在哪个块n中(除非您选择用一种基于0的索引的语言实现，在这种情况下，元素n会告诉您哪个块整数n+1在其中)。这里我用0来表示“无块”。

与这里的其他一些答案相比，这可以用时间来交换空间，但这通常是一个可以接受的权衡。

Answer 2

区间树或段树可以工作。从本质上说，您可以在间隔中进行二进制搜索，以找到包含问题点的位置。由于Segment更擅长刺杀查询，这将是我第一次尝试。

如果您正在使用Java，我以前已经用java实现了它们。您可以找到区间树和分段树。

Answer 3

我认为，对于这个问题，区间树是相当合适的。当然，实现起来要比表难得多，如果不需要动态添加块，我建议只使用表并使用简单的二进制搜索来查找块。这应该能达到与区间树相同的效率，而不会带来所有可怕的编码问题(只要您不必添加时间间隔)。