Video 9-3: §9.3 Primitive RMQ & Sparse Tables

0:00 Intro

0:02 in the next section i want to look at solutions for the range minimum query problem we'll start with the obvious things and then we'll look at one thing that's not completely trivial but still fairly easy to understand and that will also be a building block for the final solution and that's the so called sparse tables

0:23 let's first think about without spending any intelligence what can we do for this problem to set the the tone of the extremes we can do two easy things we can either do nothing at pre-processing or do everything in pre-processing and do virtually nothing at query time right these are the two extreme things you could do

0:47 the probably easiest of the two is do nothing at pre-processing time be lazy up front sounds like a very natural strategy we don't do anything at pre-processing time and when we then get a query because we did nothing earlier we have to do all the work now so we just scan this range of the array and keep track of the minimum that's not a complicated thing to do but we need to scan the entire range that we're given and the entire range could mean the entire array so because these are worst case running times the best you can guarantee for the query is linear time okay it's clear that this is the best to do if if you don't really spend time to look at the entire array during pre-processing uh there's there's really no way to um go around this any algorithm that spends less time at pre-processing a little of end time and preprocessing cannot have seen all elements of the input so if i then ask you at query time for the entire range it must scan the entire range again otherwise i can smuggle in a minimum at a position that the algorithm hasn't looked at and so then it wouldn't be correct so any correct algorithm with little o of n preprocessing time needs

2:00 to have this query time then i can also just do nothing at pre-processing if that's the same worst case right so it should be clear anything to improve on this needs to spend a substantial effort during pre-processing time let's look at something with very substantial pre-processing time

2:25 that's the opposite we don't want to do anything at query time which means we just write down all solutions up front i can do this i can create a big matrix that has for all combinations of i and j the answer precomputed in that array

2:47 i can fill this array the array has size roughly n squared but if i'm stupid and i just pre-compute each cell in individually i would get a linear contribution for each cell so you have to

3:14 and each takes it's a bit of a lie let's say each takes linear time at most and some of the cells a small fraction takes takes linear time at least and so the overall time is cubic

3:35 uh we can do the pre-processing a little smarter and then we get it down to at least quadratic would anyone like to guess how we do this it's nothing very fancy

4:01 so we're looking at at this entry mij let's use the picture up here so i and j are these these ranges now the observation is if i for example know already the the minimum in the range excluding the last one there are just two options for the minimum of the bigger range it's either whatever the minimum was in the range one smaller or it's the single new element right it's just these two options it has to be somewhere so it's either contained in this or it's this one so you can always use um a formula like this

4:51 that's formalizing what i just said you can take the previous value um i guess m is the index so is one of these two options it's either wherever the minimum was without the last one or it's the new element and this notation argumen is supposed to mean the outcome of this function is the argument where the minimum was attained so it's either this this value or j m of i j minus 1 or j and you apply this function m sorry this function a look up a and then take the argument weight was minimum it's just a convenience to write it is that confusing to anyone i could have written the same in uh a piece of code i don't feel like doing it so it's uh you take the two options and you check if one is smaller you take the first otherwise it's the other

6:54 that's easy right so we can we can use this formula if you fill the array so that the range is growing we have to make sure we have to we have free we have computed the shorter ranges first so you do an inner loop that loops over the length of the range an outer loop that loops over the range length and then a next loop that loops over i and then you fill the array that way then you can use this formula all the way through and then you get it in quadratic time

7:26 Improvements

7:30 now these are two these are two valid solutions uh but both quadratic preprocessing time is not really interesting or the linear query time is not very interesting so we want to do this a lot better and the first attempt to improve upon this is to note that you don't really need all these entries to do something quick at query time you can do away with a lot of the entries in this table m and still get very fast queries now you will have to do something at query time if you haven't recomputed all the answers so we have to figure out a compromise to do a little bit of work at query time but substantially reduce the amount of data we have to store for it and the one solution is you still store this this entry this this matrix but you leave out most of the entries you only store the ones where the length of the range l is a power of two

8:32 so you would probably want this matrix in a different format if you want to store it in memory you would have the first index as the starting position as before and the second index is the exponent of the length okay so it's just this translation i mean this would contain the same entry as m i and then j is i plus 2 to the k

9:04 because we want the length to be exactly to the decay uh if you count how many entries you have uh for each for each starting position it can be at most log n different powers of two that fit below n after you've done that many you would overshoot the length of the array and so that cannot be a valid entry so n times log base 2 of n is the num is the size of this this matrix now so you get down from quadratic to n log n that's a substantial improvement okay so that's great we know what we store but we still have to to answer queries right so it's it's not clear anymore if we can still do this because we haven't stored all the queries we haven't pre-computed all the answers

9:54 Trick

9:58 the the trick is to use something like the argument before the minimum in the range it has to lie somewhere so if we can find two overlapping or to touching regions for which we know the minimum we can just do the last step of comparing the values at this position at these two minimum positions and take whichever is the smaller and the the the trick here is to say whatever range you start with you can find a power of two namely like this so it's a power of two that lies between the length of the range and half of the length of the range and you know there always must be one otherwise uh you would have left out powers of two so you can always find a blue one that has length power of two and starts at i and you can find a green one that has the same length but ends at j they can be overlapping as in this example they could also be just touching but then you could have taken the next power of two so in a sense you can make one of these two inequalities strict and it would still work um it doesn't change the algorithm at all which there which way you break it you cover this range by the blue and

11:15 green positions some positions are double covered now the minimum in this range has to lie somewhere either in the green or the blue region potentially in both so if you take the positions of the minima of the of the blue and green region you can just take a comparison between those two numbers and then you find the minimum of the overall range okay that's that's the key idea and this helps because the the blue and green regions have a length power of two so they're one of these few entries that we stored in our table m prime specifically these are arrangement queries of these two of these two inputs and so um

12:19 so where would you find the first one it's an m prime starting at i and the length is k that's the easy one and the second one we have to convert but i've already done this here

12:37 so it's at j minus to the k plus one and then k because that's the length right we encode the exponent of the length here so again uh if you have precomputed all these m prime values at query time you t you look up these two values that's two indices in the array you take the values at this position compare them and return whichever is is the smaller one so the same construction with this argument that we've used before all right

13:18 similar to before we can do the pre-processing time so that each entry in the matrix takes constant time to compute and the trick here is again the same as before if you want to compute this next bigger value

13:39 you know that that is a range that covers i up to now if you cut that range in half you find two ranges this goes up to i plus to the k minus one minus one and then here is i plus to the k so you find two ranges that are half as long again a power of two in length so you have computed them already so you can do the same trick as before you do arcmin

14:31 so you start at i and use the one smaller a square bracket as is this the other is i plus 2 to the k and also k minus 1.

15:01 you can do the pre-processing so that the lengths increase right the outer loop is over k the inner loop is over i so you can make sure that these two are both known when you want to compute the next one so it's the same the same trick we cover the range with two

15:29 so you use the same trick over and over again minima are in a way um you can split it over different ranges and then reduce it to the to the minimum of two minima

15:46 so we overall get a solution that has constant query time that's great and n log n pre-processing time time and space that's already already quite decent now the only thing that's left is to get rid of this lock factor we want to get it down to linear okay