This past Monday, I presented the "range minimum query" (RMQ) at a workshop. It is a very interesting topic, and can be implemented in the data tracking of EdLab products. "Range Minimum Query" is a classic algorithm question, and it's variations will lead to other practical problem solving. First, what is "Range Minimum Query(RMQ)"? Given an array A[1,n] of objects taken from a well-ordered set (such as numbers), a RMQ asks for the position of a minimum element in the sub-array A[i,j]. For example, when A[0,5,2,5,4,3,1,6,3], then the answer to the range minimum query for the A[3,8] =[2,5,4,3,1,6] is 6, as A[6]=1. RMQs can be used to solve the lowest common ancestor problem, and is used as a tool for many tasks in exact and approximate string matching. In terms of the data tracking of EdLab products, it can be used to solve getting time period for the most shared articles within that period, or getting the range of age of users who are interested in watching one specific Vialogue. How to solve that problem? 1. Dynamic programming Using dynamic programming to preprocess the problem, and using query to get the solution. The preprocessing time will be O(n^2), and query time is O(1), so the overall time complexity is O(n^2). 2. Segment tree For solving the RMQ problem we can also use segment trees. A segment tree is a heap-like data structure that can be used for making update/query operations upon array intervals in logarithmical time. We define the segment tree for the interval [i, j] in the following recursive manner:

• a the first node will hold the information for the interval [i, j]
• b if i[

By using a segment tree, the time complexity to build the segment tree is O(nlogn), and the query time will only take O(logn) . So the time complexity decreases a lot compared to the first solution. Segment tree is a powerful tool, and can be implemented in various places. I will strongly recommend Sharath Gururaj to give us a lecture about that topic. For more detail of the RMQ problem, you can go to this link. Hope this helps!