Disclaimer: I will not promise that this blog will make you code lca better. binary lifting is generally better than the following algorithm and i am only sharing it since i find it very interesting.↵
↵
===================================================================================↵
↵
intro (skip this if you know what lca is)↵
==================↵
↵
if you didnt know, lca stands for least common ancestor (and implies a rooted tree). so any ancestor of a node u. is any node on u's path to the root node (including the root itself). in the diagram below nodes 1 and 2 are both ancestors of node 4. so common ancestors of nodes u and v are the nodes that are both ancestors of u and ancestors of v. the least common ancestor of nodes u and v is first node that u and v share as an ancestor (first meaning the ancestor with the largest depth). and you can see in the picture below the lca of 4 and 6 is 2, since that's the node with the furthest depth from the root that is both an ancestor of u and an ancestor of v. 1 does not count as the lca since 2 is further down and 5 does not count since it is not an ancestor of 4 (or 6 for that matter). for any pair of nodes on a rooted tree there is only one lca (hopefully this is intuitive), and this blog post describes ways to find that lca.↵
↵
↵
↵
here is an image (from google search) of a tree.↵
remember lca only works on a rooted tree since you have a sense of "up" and "down" only if there is a root↵
↵
Sqrt LCA↵
==================↵
↵
imagine if we had a function k_up where k_up(u, k) returns the k'th node up from u. so from the diagram above k_up(2, 1) is 1 and k_up(8, 2) is also 1. this will be very helpful to do lca as we will see later.↵
the array par[] stores for each u the direct parent of u (the parent of the root node is an imaginary node, 0 or -1 depending upon your implementation). in the diagram above par[2] = 1, par[5] = 2, and par[8] = 3.↵
↵
so in all of the following code assume the par array is already calcutated, as for how to calculate it.... go google it.↵
↵
↵
~~~~~↵
int k_up(int u, int k){↵
for(int i = 0; i<k; i++){↵
u = par[u];↵
}↵
return u;↵
}↵
~~~~~↵
↵
so what is the complexity of the above code? its O(k) since you loop over k to find par[u] k times. darn that's slow. i really wish we could do that faster. well that's the point of this blog.↵
↵
so now lets pick a define a constant R, all we have to know abt R is that it's a constant <= the number of nodes on the tree. now for each u we define super[u] as the parent of u R times up (super for superparent, i love that word "superparent"). in the case that going k times from u takes us higher than the tree allows supor[u] = -1. so how does this help? so now in k_up(u, k) we can first loop over floor(k/R) times the superparent then we loop over k%R times on the parent array. so in total we move up floor(k/R)*R + k%R times (or k times :OOO). now the complexity is reduced to O(k/R + R) since the first half can only take k/R turns at most and the second half can take R steps at most. below is some code of the idea↵
↵
↵
↵
~~~~~↵
int k_up(int u, int k){↵
while(k >= R) k = k/R, u = super[u];↵
for(int i = 0; i<k; i++) u = par[u];↵
return u;↵
}↵
~~~~~↵
↵
now there are a few problems, namely how to find super[] and what is R, **If we set R to be ~sqrt,2021-03-18(n), O(k/R + R) is minimized.** (hopefully the intuition makes sense), in fact picking R like this is so common its even got a name: "SQRT decomp". and to find super, you can for each u, loop up R times to find the parent R steps up. you can do this even faster, but im too lazy to cover that.↵
↵
be sure you understand all of this since the concept of a k_up function will come up a lot later in this blog.↵
↵
now onto the actual lca part. so consider a rooted tree and any two nodes u and v **that are on the same level or have the same distance from the root**. if we just marched from each node taking 1 step from each at the same time, the first node where they are the same is their lca. (note this only works if u and v start on the same level). so below is an implementation of the idea↵
↵
↵
~~~~~↵
int lca(int u, int v){ //remember that they have the same depth↵
while(u != v){ ↵
u = par[u], v = par[v];↵
}↵
return u;↵
}↵
~~~~~↵
↵
so whats the complexity of this code? **its O(d) where d is the difference of depth from the lca to node u (or v)**. this at worst case can be O(n) where n is the number of nodes in the tree (imagine a chain). so what can we do to speed it up? let us refer to the super array again. so if super[u] == super[v] then we know that the lca of u and v has to be super[u] or further down the tree. since if it was further up, we'd just take super[u] instead since super[u] is an ancestor of u and super[v] is an ancestor of v (and they are the same :O). so now (remember nodes u and v have the same depth) we can just loop over the super[u] and super[v] while they are different, and when they are the same, we'll loop over the parent array. below is the code for this idea.↵
↵
~~~~~↵
int lca(int u, int v){ //remember that they have the same depth↵
while(super[u] != super[v]){ ↵
u = super[u], v = super[v];↵
}↵
while(u != v){↵
u = par[u], v = par[v];↵
}↵
return u;↵
}↵
~~~~~↵
↵
what is the complexity of the above code? **its O(n/R + n%R) worst case. which is also O(sqrt(n)) since R is sqrt(n)**. sadly this only find the lca when the two nodes have the same depth from the root. luckily this is where our k_up function comes in handy. so if we define dep[u] as the depth of node u from the root and dep[root] = 1, then we can just set u to be the further down node out of u and v and then make u = k_up(u, dep[u] — depv]). and now it becomes lca on the same depth. below is the implementation of the idea.↵
↵
↵
~~~~~↵
int k_up(int u, int k){↵
while(k >= R) k = k/R, u = super[u];↵
for(int i = 0; i<k; i++) u = par[u];↵
return u;↵
}↵
↵
int lca(int u, int v){↵
if(dep[u] < dep[v]) swap(u, v);↵
u = k_up(u, dep[u] - dep[v]); //setting u to be the node with greater depth↵
u = k_up(u, dep[u] - dep[v]); //moving u up to the same level at v↵
while(super[u] != super[v]){ //iterating over super↵
u = super[u], v = super[v];↵
}↵
while(u != v){ //ieterating over par↵
u = par[u], v = par[v];↵
}↵
return u; //u and v will be the same, so returnv works too↵
}↵
↵
~~~~~↵
↵
since k_up is also O(root(n)) worst case, the. overall query is still O(root(n)) in time complexity.↵
↵
and our lca implemention is complete! its O(n sqrt(n)) precomp (or O(n) if you are smart abt it, try figuring out how later :D) and its O(sqrt(n)) per query. a more complete implementaion can be found [here](https://pastebin.com/yDjaQQ22) (along with calculating the par, super, and dep arrays).↵
↵
↵
Conclusion↵
==================↵
↵
the overall time complexity is O((n+q)sqrt(n)) and the memory is O(n) since we just have to store par, super, and dep arrays. but if you squish the code, it becomes a pretty short impl (and slow) and you cna make the compleixt yO(n + q*sqrt(n)) if you want.↵
↵
please remember O(sqrt(n)) for lca queries is really slow. reaaallllly slow. there are better lca algorithms but this is cool one i wanted to introduce. also note the actually fun lca algorithm (that's not bin lifiting) will be on the next blog post since this one got too long. rip.↵
↵
thank you reading and i apologize for any typos, instances of unclearness, and bugs in the code. ↵
↵
===================================================================================↵
↵
intro (skip this if you know what lca is)↵
==================↵
↵
if you didnt know, lca stands for least common ancestor (and implies a rooted tree). so any ancestor of a node u. is any node on u's path to the root node (including the root itself). in the diagram below nodes 1 and 2 are both ancestors of node 4. so common ancestors of nodes u and v are the nodes that are both ancestors of u and ancestors of v. the least common ancestor of nodes u and v is first node that u and v share as an ancestor (first meaning the ancestor with the largest depth). and you can see in the picture below the lca of 4 and 6 is 2, since that's the node with the furthest depth from the root that is both an ancestor of u and an ancestor of v. 1 does not count as the lca since 2 is further down and 5 does not count since it is not an ancestor of 4 (or 6 for that matter). for any pair of nodes on a rooted tree there is only one lca (hopefully this is intuitive), and this blog post describes ways to find that lca.↵
↵
↵
↵
here is an image (from google search) of a tree.↵
remember lca only works on a rooted tree since you have a sense of "up" and "down" only if there is a root↵
↵
Sqrt LCA↵
==================↵
↵
imagine if we had a function k_up where k_up(u, k) returns the k'th node up from u. so from the diagram above k_up(2, 1) is 1 and k_up(8, 2) is also 1. this will be very helpful to do lca as we will see later.↵
the array par[] stores for each u the direct parent of u (the parent of the root node is an imaginary node, 0 or -1 depending upon your implementation). in the diagram above par[2] = 1, par[5] = 2, and par[8] = 3.↵
↵
so in all of the following code assume the par array is already calcutated, as for how to calculate it.... go google it.↵
↵
↵
~~~~~↵
int k_up(int u, int k){↵
for(int i = 0; i<k; i++){↵
u = par[u];↵
}↵
return u;↵
}↵
~~~~~↵
↵
so what is the complexity of the above code? its O(k) since you loop over k to find par[u] k times. darn that's slow. i really wish we could do that faster. well that's the point of this blog.↵
↵
so now lets pick a define a constant R, all we have to know abt R is that it's a constant <= the number of nodes on the tree. now for each u we define super[u] as the parent of u R times up (super for superparent, i love that word "superparent"). in the case that going k times from u takes us higher than the tree allows supor[u] = -1. so how does this help? so now in k_up(u, k) we can first loop over floor(k/R) times the superparent then we loop over k%R times on the parent array. so in total we move up floor(k/R)*R + k%R times (or k times :OOO). now the complexity is reduced to O(k/R + R) since the first half can only take k/R turns at most and the second half can take R steps at most. below is some code of the idea↵
↵
↵
↵
~~~~~↵
int k_up(int u, int k){↵
while(k >= R) k = k/R, u = super[u];↵
for(int i = 0; i<k; i++) u = par[u];↵
return u;↵
}↵
~~~~~↵
↵
now there are a few problems, namely how to find super[] and what is R, **If we set R to be ~sqrt,2021-03-18(n), O(k/R + R) is minimized.** (hopefully the intuition makes sense), in fact picking R like this is so common its even got a name: "SQRT decomp". and to find super, you can for each u, loop up R times to find the parent R steps up. you can do this even faster, but im too lazy to cover that.↵
↵
be sure you understand all of this since the concept of a k_up function will come up a lot later in this blog.↵
↵
now onto the actual lca part. so consider a rooted tree and any two nodes u and v **that are on the same level or have the same distance from the root**. if we just marched from each node taking 1 step from each at the same time, the first node where they are the same is their lca. (note this only works if u and v start on the same level). so below is an implementation of the idea↵
↵
↵
~~~~~↵
int lca(int u, int v){ //remember that they have the same depth↵
while(u != v){ ↵
u = par[u], v = par[v];↵
}↵
return u;↵
}↵
~~~~~↵
↵
so whats the complexity of this code? **its O(d) where d is the difference of depth from the lca to node u (or v)**. this at worst case can be O(n) where n is the number of nodes in the tree (imagine a chain). so what can we do to speed it up? let us refer to the super array again. so if super[u] == super[v] then we know that the lca of u and v has to be super[u] or further down the tree. since if it was further up, we'd just take super[u] instead since super[u] is an ancestor of u and super[v] is an ancestor of v (and they are the same :O). so now (remember nodes u and v have the same depth) we can just loop over the super[u] and super[v] while they are different, and when they are the same, we'll loop over the parent array. below is the code for this idea.↵
↵
~~~~~↵
int lca(int u, int v){ //remember that they have the same depth↵
while(super[u] != super[v]){ ↵
u = super[u], v = super[v];↵
}↵
while(u != v){↵
u = par[u], v = par[v];↵
}↵
return u;↵
}↵
~~~~~↵
↵
what is the complexity of the above code? **its O(n/R + n%R) worst case. which is also O(sqrt(n)) since R is sqrt(n)**. sadly this only find the lca when the two nodes have the same depth from the root. luckily this is where our k_up function comes in handy. so if we define dep[u] as the depth of node u from the root and dep[root] = 1, then we can just set u to be the further down node out of u and v and then make u = k_up(u, dep[u] — depv]). and now it becomes lca on the same depth. below is the implementation of the idea.↵
↵
↵
~~~~~↵
int k_up(int u, int k){↵
while(k >= R) k = k/R, u = super[u];↵
for(int i = 0; i<k; i++) u = par[u];↵
return u;↵
}↵
↵
int lca(int u, int v){↵
if(dep[u] < dep[v]) swap(u, v);
u = k_up(u, dep[u] - dep[v]);
u = k_up(u, dep[u] - dep[v]); //moving u up to the same level at v↵
while(super[u] != super[v]){ //iterating over super↵
u = super[u], v = super[v];↵
}↵
while(u != v){ //ieterating over par↵
u = par[u], v = par[v];↵
}↵
return u; //u and v will be the same, so returnv works too↵
}↵
↵
~~~~~↵
↵
since k_up is also O(root(n)) worst case, the. overall query is still O(root(n)) in time complexity.↵
↵
and our lca implemention is complete! its O(n sqrt(n)) precomp (or O(n) if you are smart abt it, try figuring out how later :D) and its O(sqrt(n)) per query. a more complete implementaion can be found [here](https://pastebin.com/yDjaQQ22) (along with calculating the par, super, and dep arrays).↵
↵
↵
Conclusion↵
==================↵
↵
the overall time complexity is O((n+q)sqrt(n)) and the memory is O(n) since we just have to store par, super, and dep arrays. but if you squish the code, it becomes a pretty short impl (and slow) and you cna make the compleixt yO(n + q*sqrt(n)) if you want.↵
↵
please remember O(sqrt(n)) for lca queries is really slow. reaaallllly slow. there are better lca algorithms but this is cool one i wanted to introduce. also note the actually fun lca algorithm (that's not bin lifiting) will be on the next blog post since this one got too long. rip.↵
↵
thank you reading and i apologize for any typos, instances of unclearness, and bugs in the code. ↵
