鑑於是二叉樹和LCA，找到具有此LCA的一對節點的數量？

Question

考慮如下定義的無限二叉樹。

對於標記爲v的節點，讓其左邊的子節點表示爲2 * v，右邊的子節點爲2 * v + 1。樹的根標記爲1.對於所有i的（a_i < = b_i）的給定n個範圍[a_1，b_1]，[a_2，b_2]，... [a_n，b_n]每個範圍[a_i，b_i]表示一組不小於a_i且不大於b_i的整數。例如，[5,9]將代表集合{5,6,7,8,9}。

對於某個整數T，讓S表示直到n的所有i的聯合[a_i，b_i]。 我需要找到獨特的元素對X，Y在S的（不論順序）的數量，使得LCA（X，Y）= T

（維基百科有一個相當不錯的解釋什麼LCA兩個節點中的是）

---

例如，對於輸入：

A = {2, 12, 11} 
B = {3, 13, 12} 
T = 1 

輸出應該6.（的範圍是[2,3]，[12,13]和[ 11,12]，他們的聯合是集{2,3,11,12,13} （2,3），（2,13），（3,11），（3,12），（11,13）和（12,13））中的所有20個可能的對具有LCA 1.）

而對於輸入：

A = {1,7} 
B = {2,15} 
T = 3 

輸出應該6.（給出的範圍是[1,2]和[7,15]，以及它們的並集是集合{1 ，2,7,8,9,10,11,12,13,14,15}。在110種可能的配對中，正好6種（（7,12），（7,13），（12,14），（12,15），（13,14）和（13,15））具有LCA 3.）

Answer 1

嗯，這是相當簡單的計算兩個節點的LCA在你的符號，使用這個遞歸方法：

int lca(int a, int b) { 
    if(a == b) return a; 
    if(a < b) return lca(b, a); 
    return lca(a/2, b); 
} 

現在找套的結合，我們先需要能夠找到特定範圍所代表的內容。讓我們來介紹一下工廠方法：

Set<Integer> rangeSet(int a, int b){ 
    Set<Integer> result = new HashSet<Integer>(b-a); 
    for(int n = a; n <= b; n++) result.add(n); 
    return result; 
} 

這將返回含有的包含範圍內的所有整數一個Set<Integer>。

要找到這些集合的並集，只是addAll他們的元素，一組：

Set<Integer> unionSet(Set<Integer> ... sets){ 
    Set<Integer> result = new HashSet<Integer>(); 
    for(Set<Integer> s: sets) 
     result.addAll(s); 
    return result; 
} 

現在，我們需要遍歷所有可能對在集：

pairLcaCount(int t, Set<Integer> nodes){ 
    int result = 0; 
    for(int x: nodes) 
     for(int y: nodes) 
      if(x > y && lca(x,y) == t) result++; 
    return result; 
} 

其他一切只是膠合邏輯，將輸入要求轉換爲此處所採用的方法。例如，如下所示：

Set<Integer> unionSetFromBoundsLists(int[] a, int[] b){ 
    Set<Integer> [] ranges = new Set<Integer>[a.length]; 
    for(int idx = 0; idx < ranges.length; idx++) 
     ranges[idx] = rangeSet(a[idx], b[idx]); 
    return unionSet(ranges); 
}