Lca va statik rmq o'rtasidagi munosabat

LCA (Lowest Common Ancestor):

Given a pair of nodes , the common ancestor which is farthest from root. See Wiki! for better explanation.

RMQ (Range Minimum Query):

Given an array of number , return the index which is minimum between a given pair of indices.
LCA problem can be converted to RMQ problem as following

• 
  Do Euler Tour! on the given tree and stores the vertex visisted in an array E. Note that size of this array will be 2n-1 because every edge has even degree and is visited twice.
  
• 
  Store level of each vertex during Euler tour in an array L. Note that consecutive entry in this array will differe by +/- 1 [ because the euler path will eithe go down or up and this will only change level either by +1 or -1]. This too will be 2n-1
  
• 
  Store occurence of first occurence each vertex in E another array R. Size will be n as there are n vertices.
  

How to find LCA

• 
  First check in array R when these nodes occured during Euler tour traversal, this will be A and B.
  
• 
  Next you get traversal number, check in array L , the shallow node (the minium level ) going from A to B.
  
• 
  This will give travesal number , map that in E array. Because if L stores level of that node , E store node number.
  

Lets see this with an example.

LCA of node n will get converted to RMQ of 2n-1 (L array).
Problem boils down to finding RMQ in L, which can be done in multiple ways. If LCA problem contains n nodes , RMQ problem contains 2n-1 entries (because of size of array L). Time complexity = ,where f(n) is preprocessing time and g(n) is lookup time. So for n nodoes of LCA , RMQ solution will be 2n-1 nodes.

• 
  Using Table lookup
  

This is a dynamic programming approach, where we create partial solution and then use them to build further. For example to generate minimum between [0,1] we find miniumum between [0,0] and [1,1] which we know. Recursively we keep building this lookup table. Time and space complexity is O(n^2).

• 
  Using Sparse Table (ST) This is also a recursive approach but we build a lookup table in powrs of 2 starting from every index. For example for index 0 we do 0,0 -> 2^0 0,1 -> 2^1 0,3 -> 2^2 For lookup we find maximum block which span from start index to end index. Another block which span from end_index to anything after start_index but maximum. That will overlap and we will get over minimum.
  
• 
  Using Segment Tree
  
• 
  +- RMQ Algorithm for finding RMQ on Restricted array (contains only +- 1)