Video 9-3: §9.3 Primitive RMQ solutions

0:03 in this next subsection i want to discuss the simple solutions to the arrangement career problem uh the sparse arrays will be the final result for today we'll leave it just with the most primitive ideas for implementing arrangement queries

0:23 there's two obvious solutions at the extreme ends of a scale where the scale is from doing nothing at pre-processing time to doing everything at pre-processing time so one is doing nothing no pre-processing at all and whenever someone asks for a minimum in a range you just find that minimum by walking through the entire range and keeping track of the minimum that is trivial to do i'm just listing it here to translate it into our notation so that is a constant time preprocessing actually zero but okay no preprocessing constant time preprocessing linear time query because the range can be as long as the entire array that's not very interesting and it won't get us closer to our final goal the other extreme end is well there's only so many possibilities to ask for ranges namely um i and j i can start at zero and uh they have to be sorted um well now it's uh less than n because we start counting at zero so there's only n squared solutions for this n squared choices for i and j so we can create one big two-dimensional array for i and j and just store the solution for rmq there so the query is a simple is one array lookup or maybe in a two-dimensional array but you can even

2:00 map this to a 1d array if you wanted so we can compute every individual answer in linear time there's n squared answers that gives us a cubic preprocessing time but constant query it's probably not good enough to be interesting but at least it shows what is possible at the extreme ends a simple observation is that we can get the pre-processing time to quadratic so filling the array in constant time and you can do this because if you have your current range i to j uh you can take one element off the last say and then what is the possibility for the arrangement query in i to j you can find where the range min is if you leave out the j and that's maybe here so then

3:04 is either rmq i up to j minus 1 this you cannot see it's either rmq or the result is j and these are two different options so you can take constant time to compare the values at that position and then insert into your array m whichever was the smaller one so by filling the array in a somewhat smart order going from those with a small range to those with a bigger range is enough to get this result quadratic pre-processing time constant query time that's what you can easily do unfortunately this is still far away from our ultimate goal of a linear pre-processing time and we will continue tomorrow with our quest towards this goal