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

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

如果您将整数视为从最高有效位开始的位字符串，则可以使用按位 trie。trie允许您存储键值对，尽管在您的情况下您实际上不需要存储与每个整数关联的值，但它还允许有效搜索以给定前缀开头的所有条目（即以给定前缀开头） k 个最高有效位）。另一种选择是Y-fast trie。