给定 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 中插入/删除也很好 创建后。
最佳答案
如果您将整数视为从最高有效位开始的位串，您可以使用 bitwise trie . trie允许您存储键值对，虽然在您的情况下您实际上不需要存储与每个整数关联的值，但它还允许高效搜索以给定前缀开头的所有条目(即以给定的 k 最重要位)。另一个选项是 Y-fast trie .
关于algorithm - 适合基于最高有效位存储和查询整数的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40390355/