二进制表示中的最长公共前缀

Question

我们得到一棵无向树，其中 N (1 to N) 个节点以节点 1 为根。每个节点都有一个赋值，由数组表示 - A[i] 其中 i:[1:N].

我们需要回答 Q 类型的查询： -> V X : 值 V 和节点 X[=56= 的任何祖先之间的公共前缀的最长长度] 包括 X，以 62 位长度的二进制表示。

2个号码之间的公共前缀定义为：

示例：

4: 0..................0100 (62-bit binary representation) 6: 0..................0110 Considering both as 62-bit in it's binary representation. Longest length of the common prefix is: 60 (as 60 left most bits are same.)

现在我们得到 N（节点数），边，节点值（A[i] ) 和查询，我们需要在最佳时间回答每个查询。

约束：

N <= 10^5, number of nodes A[i] <= 10^9, value of each node Q <= 10^5 ,number of queries Edge[i] = (i, j) <= N

方法：

创建树并跟踪每个节点的直接父节点。

对于每个查询：[V, X]，遍历每个节点 n（在从 X 到根 的路径中）并将每个节点的值与 V 并为每个 XOR 运算找到最重要的设置位，并从中选择最小的一个。

所以查询的结果：[V, X]：62 - (1 + Step-2 结果)。

Is there any other efficient way to solve this problem? As the above approach in worst case takes O(n^2) time.

Answer 1

Java：使用numberOfLeadingZeros。类 Long 和 Integer 有一组很好的实用函数。

long commonPrefix(long x, long y) {
    return Long.numberOfLeadingZeros(x ^ y);
}

关于任何算法改进：它不会是诚实的在这里提供一个极好的解决方案。而且更好您用笔和纸解决问题，使数学方面感到困惑。事实上，我可以看到一个微小的方式。也许你可以做得更好。

Answer 2

求两个数的二进制表示长度，如果不相同则不可能有任何匹配位，所以只有前导零是公共前缀。否则我们可以通过异或值找到匹配的前缀位数。

这是一个巧妙的技巧，因为 XOR 运算会将所有匹配位变为零，直到最左边的位不匹配。因此，公共前缀的长度将是任一数字的二进制表示的总长度（因为它们的长度相同）与 XOR 值的二进制表示的长度之间的差值。

最后，由于您需要 62 位，因此您添加了前导零，前导零的数量是 62 减去任一数字的二进制表示的长度。

所以， 62 - 任一数字的长度 + 公共前缀。进一步简化意味着答案是 62 - xor 值的长度；

这里唯一棘手的情况是数字相同，您可以提前处理。

int commonPrefix(int x, int y)
    if(x == y)
        return 62;

    int xLength = Math.floor(Math.log(x) + 1);
    int yLength = Math.floor(Math.log(x) + 1);
    
    if(xLength != yLength)
        return 62 - Math.max(xLength, yLength);

    int xor = x ^ y;
    int xorLength = Math.floor(Math.log(xor) + 1);

    return 62 - xorLength;

一旦你了解了这些内容，一个简单的 DFS 应该会为你提供你正在寻找的节点的祖先，你可以通过将给定值与每个祖先进行比较来找到最长的公共前缀。

Answer 3

您可以使用 fully persistent binary search trees.

在 O((N+Q) log N) 时间内解决此问题

“持久”数据结构是一种在修改时保留先前版本的数据结构。 “完全持久”意味着以前的版本也可以修改。通常，完全持久的数据结构被实现为 purely functional data structures.

你需要一个二叉搜索树。经典示例是 Okasaki's red-black trees，但您可以从任何纯函数式语言移植任何 BST 实现。

有了这种数据结构，你的问题就迎刃而解了。

为仅包含根值的根创建单例树。
对于每个子项，通过添加子项的值从其父项创建一个新版本。
以 BFS 或 DFS 顺序继续，直到您拥有包含其所有祖先值的每个节点的树版本。这将需要 O(N log N) space 和时间。
对于每个查询 [v,x]，然后，获取节点 x 的树并找到最大值 <= x 和最小值 >= x。这需要 O(log N) 时间。
具有最长公共前缀的祖先将是您找到的值之一。通过将它们与 v 进行异或并选择最小的结果来检查它们。然后二进制搜索（或一些更快的位破解方法）找到最左边的位的位置。

注意：以上讨论假设您说“我们需要在最佳时间回答每个查询”时是认真的。

如果可以乱序处理查询，那么就不需要持久树。您可以只使用在您的语言库中找到的单个常规 BST，因为您不需要一次使用所有树。

按预定顺序遍历图形，在找到每个节点时调整树，然后处理专门针对该节点的所有查询。

Answer 4

我想到了一个可能有用的方法。您可以通过为 MSB 位集添加附加值来修改节点中的数据。例如，如果数字为 8，则考虑到 MSB 在左侧，MSB 位设置为 62 - 4 = 左起第 58 位。此外，您可以将这些位存储在 bitset 中。因此，您的树节点结构可能会被修改为（在 C++ 中）：

struct TreeNode
{
    int node_value;
    int set_msb_bit_from_left;
    bitset<62> b;
    TreeNode* left;
    TreeNode* right;
};

要点：

两个数字 x 和 y 具有相同的 set_msb_bit_from_left 如果它们落在相同的范围 [2^(n-1), 2^n) 中。所以这样的数字可以添加到一组中，比如 Gi 其中 i 是 set_msb_bit_from_left.
如果x属于Gi，y属于Gi+1，则最长公共前缀为i.
如果x属于Gi，y属于Gj和i < j，那么最长公共前缀是i.
如果 x 和 y 属于同一组，则 bit-by-bit 需要从 MSB 到 LSB 进行检查，直到发现不匹配，或使用其他一些有效的位操作技巧，如 XOR 运算。

算法：

在创建树的节点时，计算node_value的set_msb_bit_from_left。
~~基于msb_bit_from_left创建用于存储组的数据结构。这个数据结构可以是一个简单的map或者disjoint set union。~~
对于给定的两个节点 V (nth-level child) 和 X（祖先），将所有节点从 X 到 V 放在一个集合中，并根据递增的 set_msb_bit_from_left 或组进行比较id.
从集合中的最后一个（最高组 ID）到第一个元素（最低组 ID）并计算 x 和 y 之间的最长公共前缀：

获取 x 和 y 的组。
如果相同，则从 MSB 到 LSB 进行处理，直到发现不匹配或对属于同一组的所有对象执行 XOR 并 return 输出。
否则，return min(grp_id_x, grp_id_y) - 1 其中 grp_id_x、grp_id_y 是相应的 set_msb_bit_from_left 值。 -1 因为我们不想计算设置的 MSB 位。

注意：如果最后一个元素有两个或多个在同一组中，那么你只需要找到它们之间的最长公共前缀（不需要处理来自其他组的元素，最长公共前缀将小一点）。

二进制表示中的最长公共前缀

Longest common prefix in binary representation

c++

java

algorithm

math

data-structures