Talk:Range minimum query

There are several problems based on range minimum query.Generally we have lots of method but in computer science "time and memory" used matters ,so to solve the problems within time and memory limit,a very good technique is used which is implemented by various data structure and famous one segment tree.Here i am just discussing one problem that has been asked in various online programming contest and question is on spoj.The question is simple as stated. You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , ... , aj.

But when looking at constrained then no naive technique will work here.So to solve this problem we will use other technique.

A naive algorithm will not work! If we just count the frequencies of the numbers located at [i,j] every time a query is given, we will run out of time! We must do something smarter.

Suppose this is the given vector:

A[] = { -1 -1 1 1 1 1 3 10 10 10 }

Let's build freq[] like this:

freq[] = { 2 2 4 4 4 4 1 3 3 3 }

Please note that -1 appears 2 times, 1 appears 4 times, and so on. The freq[] vector can be built in O(n) time. Now we want to see what is the maximum of freq[i..j], i.e., we want to know freq[k] such that freq[k] >= freq[i] , freq[k] >= freq[i+1] , ... , freq[k] >= freq[j].

Let's do some pre-processing ( O(n lg n) ). Define f[i,j] as the index of the maximum value of freq[i .. i + 2^j - 1]. This sub-vector has length 2^j. It's easy to see that f[i,0] = i for all 0 <= i < n. Besides,

if freq[ f[i,j-1] ] > freq[ f[i+2^(j-1),j-1] ]

--- f[i,j] = f[i,j-1]

else

--- f[i,j] = f[i+2^(j-1),j-1]

Now we'll study how to improve the query time. We'll make it O(1). Let lg denote the 2-base logarithm. Define k := floor(lg(j-i+1)) and rmq(i,j) such that:

if freq[ f[i,k] ] > freq[ f[j - 2^k + 1 , k] ]

--- rmq(i,j) = f[i,k]

else

--- rmq(i,j) = f[j - 2^k + 1 , k]

Done! freq[ rmq(i,j) ] isn't necessarily the solution of a given query, but we're almost there...

Min vs Arg min

Today, I tried to fix the confusion between "min" and "arg min" in the article. From the examples, it seems that the definition should be "RMQ_A(l,r) = min_l≤k≤r A[k]". However, the actual definition uses arg min, which is moreover a set-valued function.

After changing all occurrences of "arg min" to "min", I got confused by the cited paper Bender et.al., 2005, "Lowest common ancestors in trees and directed acyclic graphs" from which a lot of contents appears to originate. In their section 2.3 (p.6), related to the article's section "Solution using constant time and linearithmic space", they say "we compute M[i,j] = min{A[k]: k = i ... i+2^j-1}", i.e. M holds minimum values from A. On the other hand, in their dynamic programming recurrence, they use the value of e.g. M[i,j-1] as an index to A; this make sense only if M holds indices of minimum values of A. (In the article "B" is used instead of "M".) I guess Bender et.al. used sloppy notation that can easily be repaired, but I don't yet know how.

So I have two questions:

1. In section "Definition", should RMQ be defined to be the minimum value or some index of it?
2. In the section "Solution using constant time and linearithmic space", is B computed to hold minimum values or indices of them?

Any comments are appreciated. - Jochen Burghardt (talk) 09:37, 13 April 2017 (UTC)

I manually ran an example on a random array A of length 16:

         0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
        -----------------------------------------------
A:      61 88 84 80 17 46 67 26 16 38 94 39 61 80 21 58  



M:       0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15         ---> i
        -----------------------------------------------
0       61 88 84 80 17 46 67 26 16 38 94 39 61 80 21 58         1
1       61 84 80 17 17 46 26 16 16 38 39 39 61 21 21  .         2
2       61 17 17 17 17 16 16 16 16 38 39 21 21  .  .  .         4
3       17 16 16 16 16 16 16 16 16  .  .  .  .  .  .  .         8
4       16  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .         16

|                                                               |
v                                                               v

j                                                               2^j

After this, I think the recurrence formula in Bender et.al. should be corrected to:

M[i,j] = M[i,j-1] if M[i,j-1] ≤ M[i+2^j-1-1,j-1] and M[i,j] = M[i+ 2^j-1-1,j-1] otherwise

This can be simplified to

"M[i,j] = min { M[i,j-1] , M[i+2^j-1-1,j-1] }".

For example, M[1,3] = min { M[1,2] , M[5,2] } = min { 17 , 16 } = 16. There should be no A[.] around M[.,.] in the recurrence. We should add a corresponding note in the article. All occurrences of "arg min" should be changed to "min" again (including mentions in English text). - Jochen Burghardt (talk) 10:12, 13 April 2017 (UTC)