algorithm - 最低共同祖先

我正在寻找全二叉树中给定两个节点（父节点x比子节点2*x和2*x+1）的最低公共祖先的恒定时间实现。
我的问题是树中有大量的节点和许多查询。是否有一种算法，它可以进行预处理，以便在恒定的时间内回答查询。
我查看了LCA using RMQ，但是我不能使用该技术，因为我不能对树中的这么多节点使用数组。
如果知道它是完整的二叉树，并且节点之间的关系如上所述，是否有人能给我快速回答许多查询的算法的有效实现。
我所做的是从两个给定的节点开始，依次找到它们的父节点（node/2）保留访问节点的哈希列表。当我们到达一个已经在散列表中的节点时，该节点将是最低的公共祖先。
但是当有很多查询时，这个算法非常耗时，因为在最坏的情况下，我可能需要遍历30的高度（树的最大高度）才能到达根（最坏的情况）。

最佳答案

编辑：
在o（log（logn））中获取共同祖先的更快方法：-

int get_bits(unsigned int x) {
  int high = 31;
  int low = 0,mid;
  while(high>=low) {
    mid = (high+low)/2;
    if(1<<mid==x)
      return mid+1;
    if(1<<mid<x) {
      low = mid+1;
    }
    else {
      high = mid-1;
    }
  }
  if(1<<mid>x)
    return mid;
  return mid+1;
}

unsigned int Common_Ancestor(unsigned int x,unsigned int y) {

  int xbits = get_bits(x);
  int ybits = get_bits(y);
  int diff,kbits;
  unsigned int k;
  if(xbits>ybits) {
    diff = xbits-ybits;
    x = x >> diff;
  }
  else if(xbits<ybits) {
    diff = ybits-xbits;
    y = y >> diff;
  }
  k = x^y;
  kbits = get_bits(k);
  return y>>kbits;

}

说明：
获取表示x&y所需的位，使用二进制搜索是o（log（32））
x&y二进制表示法的共同前缀是共同的祖先
以较大的位数表示的数字由k>>diff带到同一位
k=x^y eraze x&y的公共前缀
查找表示剩余后缀的位
按后缀位移动x或y，得到共同的前缀，即共同的祖先。
示例：

x = 12 = b1100
y = 8  = b1000

xbits = 4
ybits = 4
diff = 0
k = x^y = 4 = b0100
kbits = 3
res = x >> kbits = x >> 3 = 1

ans : 1