algorithm - 有效查找查询范围内整数的数据结构

Question

已知范围内有任意数量的不同无符号整数值。

整数值的个数是<<范围内的整数个数。

我想构建一个允许以下运行时复杂性的数据结构:

1. O(1) 中的插入
2. 插入完成后:
   • O(1) 中的删除
   • 在O(k)中获取查询范围内的所有值，k为结果值的个数(返回值不必排序)

内存复杂度不受限制。然而，天文数字上的大量内存不可用 ;-)

这是一个例子:

• 范围 = [0, 1023]
• 插入 42
• 插入 350
• 插入 729
• 插入 64
• 插入 1
• 插入 680
• 插入 258
• 在 [300;800] 中查找值；返回 {350, 729, 680}
• 删除 350
• 删除 680
• 在 [35;1000] 中查找值；返回 {42, 258, 64, 729, 258}
• 删除 42
• 删除 258
• 在 [0; 5];返回 {1}
• 删除 1

这样的数据结构甚至可能吗？ (借助查找表等)？

一个近似值我想到的是:

• 将插入的值放入桶中。 0..31 => 桶 0​​, 32..63 => 桶 1, 64..95 => 桶 2, 96..127 => 桶 3, ...

• 插入:使用简单的移位算法找到桶 ID，然后将其插入到每个桶的数组中

• 查找:使用移位算法查找起点和终点的桶 ID。查看第一个和最后一个桶中的所有值，并检查它们是在范围内还是在范围外。将所有中间桶中的所有值添加到搜索结果中

• 删除:使用移位查找桶 ID。交换要删除的值与存储桶中的最后一个值，然后递减此存储桶的计数。

缺点:如果有很多查询，查询范围小于 32 个值，每次都会搜索整个桶。

缺点2:如果范围内有空桶，在搜索阶段也会访问它们。

Answer 1

理论上来说，一个 van Emde Boas tree是您最好的选择，使用 O(log log M) 时间操作，其中 M 是范围的大小。尽管有更高效的变体，但空间使用量相当大。

实际上，论文 On Range Reporting in One Dimension 中描述了最先进的理论状态，作者:Mortensen、Pagh 和 Patrascu。

我不确定现有的下界是否排除了 O(1)，但 M 不会大到足以使区别变得重要。我将不使用 vEB 结构，而是使用 k-ary trie，其中 k 是 2 的幂，例如 32 或 64。

编辑:这是使用特里树进行范围搜索的一种方法。

让我们假设每个数据都是一个位模式(很简单；这就是 CPU 的想法)。每个子树由具有特定前缀的所有节点组成。例如，{0000, 0011, 0101, 1001} 由以下 4 元树表示，其中 X 表示空指针。

+---+---+---+---+
|00\|01\|10\|11X|
+--|+--|+--|+---+
   |   |   |
   |   |   +----------------------------+
+--+   |                                |
|      +------------+                   |
|                   |                   |
v                   v                   v
+---+---+---+---+   +---+---+---+---+   +---+---+---+---+
|00\|01X|10X|11\|   |00X|01\|10X|11X|   |00X|01\|10X|11X|
+--|+---+---+--|+   +---+--|+---+---+   +---+--|+---+---+
   |           |           |                   |
   v           v           v                   v
  0000        0011        0101                1001

一些优化很快就会变得明显。首先，如果所有位模式的长度都相同，那么我们就不需要将它们存储在叶子上——它们可以从下降路径中重建。我们所需要的只是位图，如果 k 是机器字中的位数，那么位图非常适合上一层指针曾经所在的位置。

+--------+--------+--------+--------+
|00(1001)|01(0100)|10(0100)|11(0000)|
+--------+--------+--------+--------+

为了在 trie 中搜索 [0001, 1000] 之类的范围，我们从根开始，确定哪些子树可能与该范围相交并对其进行递归。在这个例子中，根的相关 child 是 00、01 和 10。00 的相关 child 是代表前缀 0001、0010 和 0011 的子树。

对于固定的 k，来自 k 元树的报告是 O(log M + s)，其中 M 是位模式的数量，s 是命中的数量。不要被愚弄了——当 k 为中等时，每个节点占用几个缓存行，但 trie 不是很高，因此缓存未命中的数量非常小。