[Tutorial] a few strange lca algorithms with a few strange time complexities pt 1
Разница между en9 и en10, 517 символ(ов) изменены
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.↵

![ ](/predownloaded/26/d7/26d73e7e2f6172ab41099592cd2cc4b7be3afb58.jpeg)↵

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] &mdash; 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. ↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en12 Английский willy108 2021-03-19 19:03:18 2 Tiny change: '= R) k = k/R, u = sup' -> '= R) k = k-R, u = sup'
en11 Английский willy108 2021-03-18 19:43:38 8
en10 Английский willy108 2021-03-18 19:42:36 517
en9 Английский willy108 2021-03-18 03:50:02 0 (published)
en8 Английский willy108 2021-03-18 03:25:20 0 (saved to drafts)
en7 Английский willy108 2021-03-18 03:23:08 0 (published)
en6 Английский willy108 2021-03-18 03:22:50 1 Tiny change: ' algorithms and i am ' -> ' algorithm and i am '
en5 Английский willy108 2021-03-18 03:22:23 11
en4 Английский willy108 2021-03-18 03:21:15 194
en3 Английский willy108 2021-03-18 03:18:25 1600
en2 Английский willy108 2021-03-18 03:01:14 1380
en1 Английский willy108 2021-03-18 02:50:59 4124 Initial revision (saved to drafts)