data-structures - 表示分段连续范围的数据结构？

Question

假设我有一个长度为 400 的整数索引数组，我想从开头删除一些元素，从结尾删除很多元素，从中间删除一些元素，但实际上不改变原始数组。也就是说，我不想使用索引 {0...399} 遍历数组，而是想使用分段连续范围，例如

{3...15} ∪ {18...243} ∪ {250...301} ∪ {305...310}

描述这种索引范围的良好数据结构是什么？一个明显的解决方案是创建另一个“索引中介”数组，包含从连续的基于零的索引到上面的新坐标的映射，但感觉很浪费，因为其中几乎所有元素都只是顺序数字，偶尔会有一些“跳跃”。另外，如果我发现，哦，我想稍微修改一下范围怎么办？必须重建整个索引数组。不好。

注意几点:

• 范围从不重叠。如果一个新的范围被添加到数据结构中，并且它与现有的范围重叠，那么整个事情应该被合并。也就是说，如果我在上面的示例中添加范围 {300...308}，它应该将最后两个范围替换为 {250...310} .
• 简单地循环遍历整个范围应该是相当便宜的。
• 直接查询一个值应该也比较便宜:“给我映射坐标中第42个索引对应的原始索引”。
• 应该可以(虽然可能不太便宜)以相反的方式工作:“给我原始坐标中对应于 42 的映射坐标，或者告诉我它是否已映射。”

在推出我自己的解决方案之前，我想知道是否存在可以优雅地解决此类问题的众所周知的数据结构。

谢谢!

Answer 1

似乎数组或整数对列表是最好的数据结构。您可以选择该对的第二个整数是终点还是从第一个整数开始的计数。

编辑:进一步思考，这个问题正是数据库索引所要做的。如果整数对不必按数字顺序排列，则可以更轻松地处理拆分。如果数字序列必须保持有序，则需要一种数据结构，允许您将整数对添加到数组或列表的中间。

例如，当删除 10 时，拆分必须将 (6, 12) 整数对更改为 (6, 9) (11, 12)。

Besides, what if I find that, oh, I want to modify the range a bit? The whole index array would have to be rebuilt. Not nice.

没错。也许一对整数需要改变。最坏的情况是，您必须重建整个数组或列表。