algorithm - 适合基于最高有效位存储和查询整数的数据结构

Question

给定 N 64 位无符号整数，我想将它们有效地存储在数据结构 D 中，并能够执行以下查询:

给定一个整数 A，返回 D 中至少具有相同 k 个最高有效位的所有整数。

例如，如果有一个包含 3 个 64 位整数的列表:

a. 1010010000000000010000000000000000000000100000000000000000000001
b. 0000000100001000000000010000000000000000000000000000000000000001
c. 1010010100000000000000010000000000000000000000000000000000000001

查询 A 是:

1010010000000000000000010000000000000000000000000000000000000001

我们选择 k = 7

它应该返回一个包含 2 个元素的列表:

a.1010010000000000010000000000000000000000100000000000000000000001
c.1010010100000000000000010000000000000000000000000000000000000001

如果查询 A1 是:

0010010000000000000000010000000000000000000000000000000000000001

和 k = 2

它应该返回一个元素的列表:

b. 0000000100001000000000010000000000000000000000000000000000000001

如果查询 A2 是:

1110010000000000000000010000000000000000000000000000000000000001

和 k = 3

它应该返回一个空列表。

N 的大小应该在 5000 万个整数的数量级。

你能指出最合适的数据结构吗？如果我可以从数据结构 D 中插入/删除也很好创建后。

Answer 1

如果您将整数视为从最高有效位开始的位串，您可以使用 bitwise trie . trie允许您存储键值对，虽然在您的情况下您实际上不需要存储与每个整数关联的值，但它还允许高效搜索以给定前缀开头的所有条目(即以给定的 k 最重要位)。另一个选项是 Y-fast trie .