设X是一组不同的64位无符号整数std::uint64_t，每一个都被解释为表示{1,2，…，64}的子集的位集。
我想让一个函数做以下事情：给定一个 列出X中的所有B，使得B是a(当然，在C++中，这个条件只是 由于A本身不需要在X中，我相信这不是其他问题的重复。 X将随着时间的推移而增长(但不会删除任何东西)，尽管会有比添加到X多得多的查询。 我可以自由选择表示X.元素的数据结构 显然，我们可以将X表示为 X和算法有哪些好的数据结构可以有效地做到这一点<这应该是个标准问题，但我什么也找不到> 编辑：如果这太模糊，很抱歉。显然，如果X是 假设在大多数情况下，B的数目比2^m(a的子集的数目)和|X|都小很多。因此，我们希望某种算法在比|X|或2^m小得多的时间内运行，在这种情况下，理想情况下在时间O(B的数量)内运行，但这肯定太乐观了。显然，O(|X|)在最坏的情况下是不能被打败的。 显然，预计X会有一些内存开销，而且内存对我来说比时间更不成瓶颈。使用大约10*的内存(X的内存存储为 显然，C++的使用并不重要：算法/数据结构是这里的重要内容 在X是固定的的情况下，也许Hasse图可以工作。 看起来每当X增长时，构建Hasse图都会非常耗时。(但如果没有其他结果，仍然值得一试)编辑：也许更新不那么慢，比我想象的要好。 到目前为止，以下只是我的想法也许可以找到更好的东西？ 最终编辑：由于它已经关闭，可能相当公平-；重复"；这个问题很接近——我不会再做任何编辑了。我可能会做以下操作，但使用概率跳过列表结构而不是 使用普通数字顺序将X表示为64位无符号整数 例如，我的查询元素是A=1001010。包含第一位的A的子集位于包含区间[1000000010011010]中 包含第二位但不包含第一位的A的子集位于区间[000001000000011010]中 具有第三位但不具有第二位的那些在[0000010001010]中 具有第四位但不具有第三位的位在[000000010100000010]中 现在，在第一个区间[1000000010011010]内，您可以根据第二个位创建两个子区间进行搜索：[1000000010001010]和[100000010011010] 因此，您可以用这种方式递归地分解它。搜索间隔的总长度一直在变小，所以这肯定会比通过所有X的平凡线性搜索在渐近上更好。 例如，如果X=｛00000010，00001000，00110111，10011100｝，则只有第一、第三、第四深度-1区间与X有非空交集。最终返回的结果为[000000010，00001000] 当然，如果X元素分布得相当均匀，这是不平衡的。我们可能希望搜索间隔在每个深度上具有大致相等的宽度，但事实并非如此；上面，我认为四个depth-1搜索区间的大小是27、11、3、1，对于较大的N，差异可能会大得多 如果查询集A中有k个比特，则必须在深度1处构造k个初始搜索间隔(在一个比特上搜索)，然后在深度2处构造2k个搜索间隔，在深度3处构造4k个搜索区间，等等。 如果我说得对的话，由于log|X|=O(N)，搜索间隔的数量是O(k+2k+4k+…+2^N.k)=O(k^2)=O 当然，完整的算法不是O(N^3)，因为每个区间可能包含许多元素，所以列出它们通常不会比O(2^N)更好，但让我们忽略这一点，并假设没有足够的X元素来压倒O(N^ 3)估计 另一个问题是， EDIT：另一个问题的答案显示了如何具有类似std::uint64_ta，不一定在X中，(A & B) == B)std::set或std::uint64_t的排序std::vector，我在下面给出一个算法。但我们能做得更好吗？std::set，我们可以搜索a的所有子集，花费时间O(2^m-log|X|)，其中m<=N、 或者X在时间O中的所有元素(|X|log|X|)。std::set)是可以的。比这多得多的太多了。(渐进地说，任何超过O(|X|)或O(|X|log|X|)内存的东西都可能太多)。std::set，并增加跳过距离(，这样你就可以快速计算一个区间中还有多少X元素，从而减少搜索区间的数量，当交集变小时切换到线性搜索)。这类似于这个问题中给出的顺序统计树，但跳过列表比std::set更容易重新实现(，尤其是因为我不需要删除)。std::uint64_t的std::set或排序的std::vector，并在越来越小的间隔内进行递归搜索std::map无法告诉您一个区间内有多少元素(与排序的std::vector不同)，因此您不知道何时中断分区并搜索区间中所有剩余的X元素。当然，X元素的数量(整个区间的大小)有一个上限，但它可能很差std::set的结构，该结构还可以快速提供一个范围内的元素数量，显然可以适用于类似std::map的结构。这在这里对修剪很有效(尽管很烦人，对于C++，你必须重新实现大部分std::map！)
解决方案
将整数视为0和1的字符串，使用以下规则构建patricia树的自定义版本：
- 在查找过程中，如果
1是分支的当前输入位，则继续向下两个子树
到达的所有有效叶节点的集合将是答案。
复杂性
设n为X的大小，
时间：O(n)
- 最坏情况
-1，当遍历所有子树时。复杂性受节点总数的约束，如下所述
空间：O(n)
- patricia树中的节点数正好是2n-1
基本原理
假设匹配条件为(A & B) == B，则真值表为：
| A0 | |
|---|---|
| B0 | T |
| B1 |