Lowest common ancestor

Question

I am looking for a constant implementation of the minimum common ancestor given by two nodes in a complete binary tree (parent x than child 2 * x and 2 * x + 1).

My problem is that there are a lot of nodes and a lot of queries in the tree. Is there an algorithm that preprocesses so that requests can be answered in constant time.

I looked at the LCA using RMQ , but I cannot use this method since I cannot use an array for this many nodes in the tree.

Can someone give me an effective implementation of the algorithm for quickly answering many queries, knowing that this is a complete binary tree, and the connection between the nodes is given above.

What I did was start with two given nodes and sequentially find their parents (node ​​/ 2) to save the hash list of visited nodes. when we reach a node that is already in the hash list, than node will be the lowest common ancestor.

But when there are a lot of queries, this algorithm takes a lot of time, as in the worst case I may need a height of 30 (maximum tree height) to reach the root (worst case).

Answer 1

Edit: -

A faster way to get common_ancestor in 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;  

}

Explanation: -

• get the bit needed to represent x and y, which using binary search is O (log (32))
• x y
• , , k → diff
• k = x ^ y erases 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

Answer 2

, LCA :

• , 1 , .
• , .

2 :

if a>b:
    a = shift_right(a,log2(a)-log2(b))
else:
    b = shift_right(b,log2(b)-log2(a))

XORing 2 ( 1):

if a==b:
    return a
else:
    return shift_right(a,log2(xor(a,b))+1)

- 2 O (log (word_size)) , , .

. 2: log2 64-