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↵
↵
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[U][I] !=-1 && sparse_table[U][I] != sparse_table[V][I])↵
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.↵
//we swap to make sure U is deeper than V ↵
find a number , log such that 2^(log+1) > depth[U]↵
F↵
~~~~~↵
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↵
F↵
~~~~~↵
for(I = log; i>=0; i--)↵
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.↵
↵
↵
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↵
↵
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[U][I] !=-1 && sparse_table[U][I] != sparse_table[V][I])↵
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.↵
//we swap to make sure U is deeper than V ↵
find a number , log such that 2^(log+1) > depth[U]↵
~~~~~↵
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--)↵
~~~~~↵
↵
↵
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.↵
↵
