Writing this tutorial to further my understanding in the RMQ topic LCA(Lowest Common Ancestor)

Prerequisites :

DFS and similar( concept of depth and parent )

Definition:

Given two nodes of a rooted tree, the first common ancestor they meet as they climb to their parents is the lowest common ancestor.

It’s needed to answer some tree queries like the smallest edge for the path U to V, or the largest edge or the sum, etc.

Theory :

If we have an information table for each node like, for each node X, who is X’s 2^k th parent. If they exist, good, if not, -1. how can we use this information to our advantage? Suppose we want to know the largest edge from U to V Naturally, we want to climb to the LCA of U and V, and while we’re climbing, we want to see the costs of each edge, and store the largest one.

but we don’t have to check all edges. suppose, the node U has to climb 37 parents to reach its LCA with V. now, 37’s binary is 100101 (32 + 4 + 1) what we do is, from U, we directly know, the cost of going to 32nd(2^5th) parent, from the table we will build shortly. Then from there, we will choose the 32nd parent’s 4th parent, and then its parent. so in total, we needed to have three comparison to not only climb to the LCA but also, calculate the max path length.

So how do we complete the rest of the algo? Well, first we pick U and V, and see who is deeper with respect to the root. We grab him , suppose U, and we make him climb, till he is in the same depth as V. then until they both become the same, we make them both climb.

How do we make them same depth? Well, the difference of their depth , turn it into a binary number and climb.

Btw, the table I was talking about is called sparse table. It's pretty neat.

So how do we implement this? Let’s first just see if we can find LCA of two nodes U and V

Implementation:

1. Run a dfs and calculate a few things, for all X depth[X] , parent[X]{for the root it’s -1}

2.

for(I = 1; I <= N; I++)sparse_table[I][0] = parent[I];

here, sparse_table[X][Y] is X’s 2^Yth parent. -1 if it doesn’t exist.

Question, what’s the biggest 2^Y we can have, such that at least one node has 2^Y th parent? floor(log2(n)) because, in worst case of a skewed tree of depth n, the last node’s greatest parent is log2(n) and it can never be larger than that. So floor.

so we did some pre-processing with the sparse_table, we now know, the 2^0th parent of all the nodes. now on to more

3.

for(I = 1; I <= N; I++)
   for(J = 1; (1 << J) < N; J++)
    if(sparse_table[I][J-1] !=-1)
        sparse_table[I][J] = sparse_table[sparse_table[I][J-1]][J-1];

The third line basically says if, I has a 2^(j-1)th parent. Meaning, Suppose, j = 5. I = 1. Does, I have a 2^4th parent? Yes? Ok, then 1’s 2^5th parent is 1’s 2^4th parent’s 2^4th parent. because, 1’s 2^4th parent’s 2^4th parent is 2 x 2^4 = 2^5 this is the key relation that makes it N log N so we have the sparse table ready. If you don’t get the above line, just draw a skewed tree with 9 nodes. the last node’s 2^3 rd parent will be its 2^2nd parent’s 2^2nd parent. Now time for the LCA function itself.

first. Make them same depth.

find a number , log such that 2^(log+1) > depth[U]

we swap to make sure U is deeper than V

for(I = log; I>=0; I--)
   if(depth[U] – (1 << I) >= depth[V])U = sparse_table[U][I];

If we can make this leap to U’s 2^I th parent, then do so, as long as U’s new depth is equal or deeper than V Now, for trivial case, when LCA of U,V is V itself, climbing will make U equal to V, so if that happens,V is the answer. Otherwise

for(I = log; I>=0; I--)
   if(sparse_table[U][I] !=-1 && sparse_table[U][I] != sparse_table[V][I])
      U = sparse_table[U][I];
      V = sparse_table[V][I];

so what we just did was, if U’s 2^Ith parent exists, and their parents are not the same, then make them both climb. currently, U and V are gonna be one step below their LCA, because of the condition we put answer will be parent[U]

If you understood till this part, well, for the min cost, max cost, just keep an extra info in the sparse_table, of cost_table[x][y] = max or min cost of going to X’s 2^Yth parent. Rest should be easy for you. thanks.