二進制表示中的最長公共前綴

尋找時間復雜度 <= O(nlog(n)) 的最優解的詳細解釋

我們得到一個無向樹，其N (1 to N)節點以 node 為根1。每個節點都有一個分配給它的值，由陣串列示 - A[i]where i:[1:N]。

我們需要回答Q以下型別的查詢： -> V X: valueV和節點的任何祖先之間的公共前綴的最長長度，X包括X62 位長度的二進制表示。

兩個數字之間的公共前綴定義為：

例子 ：

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

方法 ：

1. 創建樹并跟蹤每個節點的直接父節點。
2. 對于 Each Query : [V, X]，遍歷每個節點n（在從X 到 root的路徑中）并將每個節點的值與每個節點的值進行 XORV并找到每個 XOR 操作的最高有效設定位，并在所有這些中選擇最小的一個。
3. 所以查詢的結果[V, X]:: 62 - (1 Step-2 結果)。

有沒有其他有效的方法來解決這個問題？由于上述方法在最壞的情況下需要O(n^2)時間。

uj5u.com熱心網友回復：

您可以使用完全持久的二叉搜索樹在 O((N Q) log N) 時間內解決這個問題。

“持久”資料結構是一種在修改時保留先前版本的資料結構。“完全持久”意味著以前的版本也可以修改。通常，完全持久的資料結構被實作為純函式資料結構。

你需要一個二叉搜索樹。經典示例是Okasaki 的紅黑樹，但您可以從任何純函式式語言移植任何 BST 實作。

有了這種資料結構，你的問題就很容易解決了。

1. 為僅包含根值的根創建單例樹。
2. 對于每個子項，通過添加子項的值從其父項創建一個新版本。
3. 以 BFS 或 DFS 順序繼續，直到您擁有包含其所有祖先值的每個節點的樹版本。這將需要 O(N log N) 空間和時間。
4. [v,x]然后，對于每個查詢，獲取節點的樹x并找到最大值<= x和最小值>= x。這需要 O(log N) 時間。
5. 具有最長公共前綴的祖先將是您找到的值之一。通過對它們進行異或v并選擇最小的結果來檢查它們。然后二進制搜索（或一些更快的位黑客方法）找到最左邊的位的位置。

注意：上述討論假設您說“我們需要在最佳時間回答每個查詢”時是認真的。

如果您可以亂序處理查詢，那么您就不需要持久樹。您可以只使用在您的語言庫中找到的單個常規 BST，因為您不需要一次使用所有樹。

按預先順序遍歷圖形，在找到每個節點時調整樹，然后處理專門針對該節點的所有查詢。

uj5u.com熱心網友回復：

Java：使用numberOfLeadingZeros。Long 和 Integer 類有一組很好的實用函式。

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

關于任何演算法改進：在這里提供極好的解決方案是不誠實的。最好是用筆和紙解決問題，讓數學方面感到困惑。事實上，我可以看到一個微小的方式。也許你可以做得更好。

uj5u.com熱心網友回復：

我想到了一個可能有用的方法。您可以通過為 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;
};

要點：

1. 如果兩個數字 x 和 yset_msb_bit_from_left落入相同的范圍 [2^(n-1), 2^n)，則它們相同。所以這樣的數字可以加到一組中，比如的值Gi在哪里。iset_msb_bit_from_left
2. 如果 x 屬于Giy 屬于Gi 1，最長公共前綴是i。
3. 如果 x 屬于Giy 屬于Gjand i < j，則最長公共前綴是i。
4. 如果 x 和 y 都屬于同一組，則需要從 MSB 到 LSB 進行逐位檢查，直到發現不匹配，或者其他一些有效的位操作技巧，如 XOR 運算。

演算法：

1. 在創建樹的節點期間，計算set_msb_bit_from_left的node_value。
2. 基于msb_bit_from_left.創建一個用于存盤組的資料結構。這個資料結構可以是一個簡單的映射或不相交的集合聯合。
3. 對于給定的兩個節點 V（第 n 級子節點）和 X（祖先節點），將所有節點從 X 到 V 放入具有基于增加set_msb_bit_from_left或組 id 的比較器的集合中。
4. 從最后一個（最高組 id）到集合中的第一個元素（最低組 id）并計算 x 和 y 之間的最長公共前綴：

• 獲取 x 和 y 的組。
• 如果相同，則從 MSB 到 LSB 進行處理，直到發現不匹配或對屬于同一組的所有內容進行 XOR 并回傳輸出。
• 否則，回傳min(grp_id_x, grp_id_y) - 1where grp_id_x，grp_id_y是各自的set_msb_bit_from_left值。-1因為我們不想計算設定的 MSB 位。

注意：如果最后一個元素有兩個或兩個以上在同一個組中，那么你只需要找到它們之間的最長公共前綴（不需要處理來自其他組的元素，最長公共前綴會更小）。

uj5u.com熱心網友回復：

找出兩個數字的二進制表示的長度，如果不相同則不能有任何匹配的位，所以只有前導零是公共前綴。否則我們可以找到 XOR 值來找到匹配前綴位的數量。

這是一個巧妙的技巧，因為 XOR 操作會將所有匹配位都變為 0，直到最左邊的位不匹配為止。因此，公共前綴的長度將是任一數字的二進制表示的總長度（因為它們的長度相同）與 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 應該給你你正在尋找的節點的祖先，你可以通過將給定的值與每個祖先進行比較來找到最長的公共前綴。

標籤：爪哇 C 算法 数学 数据结构

上一篇：2個節點碰撞的時間

下一篇：為什么我的代碼只顯示陣列中的最后一個元素，即使它應該顯示具有最多字符的元素