堆叠间隔的数据结构
我有一个积分宽度的项目列表，可以解释为从左到右堆叠在一起的间隔。例如，假设项目是A、B、C、D、E和F，宽度分别为5、2、2、3、2和4：
项目下面的数字表示从列表开始的偏移量。
我正在寻找一种能够有效支持这些操作的数据结构，理想的情况是在O（n）以内：
- 在给定位置从中查找项目。例如，位置11处的项目是D，因为它的跨度从9到12，而位置14处的项目是F，因为它从那里开始
- 在任意两个现有项目之间插入项目，或删除任何现有项目。这将改变后续项目的位置。例如，删除项目E应导致项目F向左移动两个位置，以便从12到16
我在考虑使用类似于跳过列表的东西，每个级别存储它在下面级别中包含的宽度，但我不太确定我可以获得什么性能特征。
有什么建议吗？
共有1个答案
绳子的一种变体怎么样。
但它不是在叶子上有线，而是有间隔。
找到包含特定位置的间隔将是O（log n）（只需修改rope的索引算法以返回叶子，而不是索引到叶子中）。
在任意位置插入一个项将是O（logn）（通过拆分一次并连接两次，所有操作都需要O（logn））。
与skiplist不同，skiplist本质上是概率的，如果遇到一些坏运气，它会有O（n）个最坏的情况，这些操作将有O（log n）个保证（假设使用O（log n）平衡串联）。
-
问题内容： 问题：给定一组任意时间间隔的时间，将所有重叠的时间间隔合并为一个，然后输出结果，该结果应该只有互斥的时间间隔。为了简单起见，将间隔表示为整数对。例如，让给定的间隔集为{{1,3}，{2,4}，{5,7}，{6,8}}。间隔{1,3}和{2,4}彼此重叠，因此应将它们合并并成为{1，4}。同样，{5，7}和{6，8}应该合并并成为{5，8} 编写一个函数，该函数为给定间隔集生成合并间隔集
-
问题内容： 我正在寻找一种方法来反向旋转数据框。据我所知，pandas提供了一种pivot或pivot_table方法将EAV df转换为“普通”方法。但是，还有一种方法可以做逆运算吗？ 所以给定数据框： 我想将其转换为（EAV模型）： 这样做最有效的方法是什么？ 问题答案： 假设是索引，将执行以下操作： 如果不是索引，请像这样设置：
-
我在为考试学习时发现了我无法处理的问题： 设计一个用于处理（封闭）间隔的数据结构，它将提供三个操作： 插入（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的边界匹配，因此在上面的示例中，不会有一