用于检查项目是否在间隔范围内的概率数据结构

Question

我正在尝试解决以下问题：

给定一组区间[[s1，e1]，[s2，e2]，[s3，e3]，[s4,34]，…]如果每个间隔由开始和结束组成，并且所有间隔都是不相交的，则说明点X是否属于其中一个间隔，是否在允许误报但不允许误报的恒定时间内，并使用与输入无关的恒定内存量[此类散列等…]

因此，bloom filter主要可用于点查询，但将每个点存储在bloom filter中的时间间隔中效率不高，使用Trys将产生对数运行时，而且内存使用量应保持不变，且与时间间隔计数无关[超参数]

我试图通过调整现有DS来查找现有DSor，但找不到类似的DS，所以有什么建议如何解决这个问题吗？

Answer 1

我会尝试使用稍微修改过的“Golomb压缩序列”（GCS）（请参阅“缓存、哈希和节省空间的Bloom过滤器”/F Putze，P Sanders，J Singler）。您可以存储开始/停止对，而不是单个条目。

你需要把地面军事系统分成几个部分。每个块都包含一定的范围。因为开始/停止对可能不在同一块内，所以对于每个块，您需要存储一个额外的位，以便知道第一个条目是开始或停止块。每个区块都需要单独维护和更新。更小的块意味着更新更快，但也需要更多的空间，因为每个块都有开销。也许您想将每个块维护为一个单独的数组，然后需要一个指向所有块的指针数组。

静态GCS的示例实现在这里。但是它不包含开始/停止对。