Range Minimums and Maximums

WARNING!!! The following algorithm is incorrect! For a counter example consider the set { 9 , -10 , -10 , 5 , 5 }. It will say that the answer to Q(1 , 5) is 9, but it is fact 10. However, though it is incorrect it does provide you with a good place to start.


At first I was going to talk about the SPOJ problem ORDERS in this post, but decided to put that off. Mainly because I found something else more interesting in addition to the fact that I still haven't completely finished ORDERS.


First off, here is a link to a TopCoder tutorial on RMQ (range minimum query). This post is by no meant a substitute for the tutorial. I would recommend reading the tutorial after this post (only because you are already here) to see more on the topic. Now the problem I will be discussing is GSS1. I would like to point out at this time that the solution I am going to give WILL NOT GET ACCEPTED!! It is far too slow, but should give you a good idea on where to start or proceed.

So suppose we were naieve and decided to do all our preprocessing at the beginning and then ansewr each query in O(1). Obvioulsy the first data structe we think of is an array. So we will let Ans[i][j] be the answer to the query Q(i,j).
Now how does one go about creating this array? Well obviouly the answer to Q(i,i) is the input[i], where input[] is the given array, so

Ans[i][i] = input[i].

Now suppose that we know the value of A[i][j] how would we find Ans[i][j+1]? Well, there are three possibilities.

1. Ans[i][j+1] = Ans[i][j]
2. Ans[i][j+1] = input[j+1]
3. Ans[i][j+1] = Ans[i][j] + Sum(input, k+1, j+1)
   

In the above k is the index of the last element that is used to make A[i][j] (more on this in the example later on). So using this we can build our array Ans[][] in O(n^2), which actually isn't that bad for small cases.

EXAMPLE:
input = { 1 , 2 , -2 , 4 , -1 , 1 }

So Ans[][] will be a 6x6 array.

Ans[1][1] = 1 clearly. Now for Ans[1][2], we can either use Ans[1][1], only use input[2] or add to Ans[1][1]. So in this case we will want to add to Ans[1][1], thus giving Ans[1][2] = 3. Note that k was 1 so Sum(input, k+1, j+1) = 2

Now for Ans[1][3] we have the following cases;

1. Ans[1][3] = Ans[1][2] = 3
2. Ans[1][3] = input[3] = -2
3. Ans[1][3] = Ans[1][2] + Sum(input, 3, 3) = 3 - 2 = 1

So trivially we want Ans[1][3] = Ans[1][2] = 3.

Just for good measure consider Ans[1][4];

1. Ans[1][4] = Ans[1][3] = 3
2. Ans[1][4] = input[4] = 4
3. Ans[1][4] = Ans[1][3] + Sum(input, 3, 4) = 3 -2 + 4 = 5

Thus it is best to take all the elements in this case giving Ans[1][4] = 5. And you continue this process.

Well here is the C++ code that you have been waiting for (unless you like some other language). Once again I would like to say that this method WILL NOT WORK!! for the case on SPOJ. (note I assume that the first element of the array input[] is 0, just to make things easier to code)

Ans[n+1][n+1];
memset(Ans,0,sizeof(Ans));//not needed but I just like to know what's in my arrays

for( int i = 1; i!=(n+1); ++i)
Ans[i][i]=input[i];

for( int i = 1; i!=(n+1); ++i)
for( int j = i+1; j!=(n+1); ++j)
   Ans[i][j]=my_max(Ans[i][j-1],input[j],Ans[i][j]+Sum(input,k+1,j));

I'll leave the implementation of my_max( ) and Sum( ) up to you, along with a way to keep track of k. Note that you will need to be "creative" when making Sum( ) so that the above stays O( n^2) and doesn't become O( n^3).

In the link to the tutorial at the beginning of this post he describes other methods to solve this problem. Some have much better performance. The one I plan on using has preprocessing time O( n) and answers queries in O( log n). Some of the other methods that he claims are easy to code (though I would disagree) have preprocessing time O( n) and answers queries in O( sqrt(n)) and preprocessing time O( n log n) and answers queries in O(1).