- a the first node will hold the information for the interval [i, j]
- b if i[
Oct 10 2012 - 10:44 AM
Range Minimum Query (RMQ)
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: