用于点间隔查找的快速数据结构
我现在正在研究一个有趣的问题，我想知道是否有人成功地实现了高性能的解决方案。
我有一组“区间”，意思是一个数组，每个数组的形式
Intervals = [
[min_val_1, max_val_1],
[min_val_2, max_val_2],
...
[min_val_n, max_val_n]
]
所有这些值都是实值。现在我有一个数字，我想问，哪些区间包含这些数字？我需要能够很快回答这个问题。我可以根据需要进行预处理，空间比时间更重要。你会推荐什么方法？提前谢谢！
共有1个答案
我建议使用区间树
-
我在为考试学习时发现了我无法处理的问题： 设计一个用于处理（封闭）间隔的数据结构，它将提供三个操作： 插入（x，y）-添加间隔[x，y] 移除（x，y）-移除间隔[x，y] Count（x，y）-计算纯粹包含在区间内的区间数[x，y] x、 y是从1到n的整数。所有操作最多需要O（（log n）2） 有人能帮忙吗？
-
有数百万个不重叠的连续间隔，如[a，c]、[c，e]、[e，g）……它们以随机顺序发送给我，我想随时查询是否可以用接收到的这些连续间隔的组合来封闭其他给定间隔。 例如，我希望有一个方法来添加一个连续的间隔，一个方法来测试一个任意的间隔是否可以被之前添加的间隔组合所包围。 类似于 想知道什么是适合这种情况的数据结构？ 如果有区别，我们可以假设的边界总是与一些s的边界匹配，因此在上面的示例中，不会有一
-
我的程序在一秒钟内接收来自不同类型的数千个事件。例如，拥有数百万不同IP地址的用户可以在一秒钟内访问100k API。我想保持统计数据，并限制1分钟、1小时、1天等时间内的访问次数。所以我需要每个用户在最后一分钟、一小时或一天内的事件计数，我希望它像一个滑动窗口。在这种情况下，事件类型是用户地址。 我开始使用时间序列数据库，流入数据库;但它未能每秒插入100k个事件，并且聚合查询以在一分钟或一小时
-
我有一个积分宽度的项目列表，可以解释为从左到右堆叠在一起的间隔。例如，假设项目是A、B、C、D、E和F，宽度分别为5、2、2、3、2和4： 项目下面的数字表示从列表开始的偏移量。 我正在寻找一种能够有效支持这些操作的数据结构，理想的情况是在O（n）以内： 在给定位置从中查找项目。例如，位置11处的项目是D，因为它的跨度从9到12，而位置14处的项目是F，因为它从那里开始 在任意两个现有项目之间插入
-
java中是否有内置的数据结构可以为排序列表提供高效的性能？我还需要修改排序列表，包括插入和删除操作。我首先使用arraylist。我认为在插入和删除的情况下，arraylist的性能可能不够好。什么样的数据结构适合使用？如果没有足够快的内置数据结构，在设计自定义数据结构之前，我可以朝哪个方向走？
-
我正在尝试解决以下问题： 给定一组区间[[s1，e1]，[s2，e2]，[s3，e3]，[s4,34]，…]如果每个间隔由开始和结束组成，并且所有间隔都是不相交的，则说明点X是否属于其中一个间隔，是否在允许误报但不允许误报的恒定时间内，并使用与输入无关的恒定内存量[此类散列等…] 因此，bloom filter主要可用于点查询，但将每个点存储在bloom filter中的时间间隔中效率不高，使用T