Lca va statik rmq o'rtasidagi munosabat

+- RMQ method

Divide the array L in blocks and then precompute minimum in each block. Blocsize is choosen as log (n) /2. This bring time & space complexity to O(n). Sparse table whose time complexity is O(n logn) , replace n by log (n)/2 , we get O(n). For Computing table M, since array L contains 0,1 and is divided in blocks. There can be 2^blocksize possible combination. To build each of those combination we need a nested loop that would take blocksize².
Total time = blocksize² * 2^blocksize , which is O(n) [blocksize = log (n) / 2

RMQ to LCA

RMQ problem can be converted to generalized RMQ problem by first converting it to LCA problem and then can be solved using above way. We use cartesian tree to convert RMQ to LCA
What is Cartesian Tree A tree that can be build from an array which satisfy

• 
  min-Heap or Max Heap property
  
• 
  an inorder travesal yield the orignal array.
  

This is how we can convert an array into a cartesian tree. 
Reference