Video 9-4: §9.3 Sparse table RMQ

0:03 we left off in the last s in the last video um after discussing these very trivial solutions where you either don't do any pre-processing that was the scan-on-demand solution whenever someone asks for arrangement query you just scan the range in the array that's fine except that the range can be the entire array and so the query time is not that great the opposite extreme was we pre-compute every possible query because there's um essentially n squared choices for i and j and squared over two because they are ordered uh but let's not be too picky um you have essentially a quadratic number of choices of range minimum queries for a given array so we might as well pre-compute the answers to all of them and store them in one big array that was the the precompute all solution the query then becomes trivial you just look up the uh corresponding value but the pre-processing time goes up cubic naively but you can do it at least in in quadratic time if you're a little smart on it but of course that's not quite good enough these two solutions are simple how can we possibly improve upon that it seems you have to do some storing of of precomputed values to get along but how can you

1:28 save on the space and notice here this this running time of the preprocessing step is as good as possible as long as we store all of the solutions we already spent just a constant time per entry of this array so the time of preprocessing is basically dominated by the time we need to write the results the right to write our data structure which consists of this large array so the the question can also be phrased as how can we reduce the space usage of this data structure and that's what we'll look at next there is uh one simple nice trick that's not very complicated but it does get a significant reduction in the space and that's the first non-trivial idea on this topic so let me also slow down a little bit despite all the copy i had we'd like to do something like the pre-compute all solution but we don't want to keep all entries we need to reduce the space so we only store the entries the minimum index for i and j for certain combinations of i and j namely if the length of the range that we span is a power of two that's what this condition expresses in formulas but really it says only if i and j have distance at power

2:52 of 2 we store this entry for any other ranges we don't store the entry we still have n choices for i but then for any fixed i we only have log n choices for j because the total length is n there's only roughly log n powers of 2 between the numbers 1 and at n so the number of entries is n log n instead of quadratic that's a significant achievement and there's even a smart way to store these entries by choosing a different index instead of choosing beginning index and end index we now choose beginning index and power of the length of the range right that's that's the same k as here but that's um that's not the the tricky part the tricky part now is we only store a couple of these entries how can we still solve any possible arrangement query

3:59 so how do we do this and uh it's fine that i'm hiding part of the solution at the moment i want you to focus on the picture first anyways the the trick will be that we can use the information to puzzle together the answer of the overall query from a small number of queries that we do have and in this case this red range is the actual query we're interested in and it stretches from 5 to 18 so that's a a length of 14 if i'm not mistaken um and that's not a power of 2. 14 is not a power of 2 so we don't have this value precomputed what we do have is starting at i we have the 8 length range that's the blue one and we have this green range is also length 8 which ends with 18 with position 18. now uh in general we can always find some power of two that's uh between the total length of the array if we have exactly a power of two we don't need to do anything smart at the other extreme it could be so that we just touch with the green and the blue part actually they always overlap by one otherwise you would have a next smaller power of 2. um but doesn't

5:24 really matter they it would be enough if they just touch so how can we puzzle together our arrangement query from this well it's easy the minimum in the overall red range must be somewhere in that range by definition and in particular it can be in the blue range or it can be in the green range or it can be in the overlap but no matter where it is it's either one it's one of two numbers it's either the minimum of the blue range or the minimum of the green range right that's the property of the minimum if i have the smallest number in the blue range and the smallest in the green range i can compare those two and then the smaller is also the minimum of the entire red range and so that's spelled out here a little bit more carefully with the indices worked out we define our k like this so that we have a power of two that's between the length of the range and half of that and then we can cover this range by two ranges that have a power of two in length a blue and a green one as shown in the picture and you can work out what their indices are and then the um arrangement query the

6:40 red uh big query that we're interested in so this is the red box that is the smaller of these two so it's well arcmin says it's uh either rmq1 or rmq2 whichever makes a off rmq1 arm q2 smaller okay so that's just a fancy way of writing if this is smaller than return rmq1 if a of rmq2 is smaller return iron cube2 and these two are just um the arrangement queries from the blue and the green range and these we have stored so uh we can use our lookup table to obtain the answers to the green and blue recursive query it looks recursive but it's not really recursive this is something we've stored in our table and to be explicit we could actually give the exact entry here if we had the space

7:46 maybe i put that here so we take the starting index in the first coordinate and then the second coordinate is just the length so that's actually easier than specifying the arrangement query and we can do the same thing for the other one here it's not quite as nice because we have to copy this nasty expression for the starting index but still not too bad

8:11 that way so this is just two table lookups and then uh finding which one is smaller is just uh looking at these two positions in the array and returning the smaller one

8:28 that was still fairly easy to do right but we got the space down from n log n from n squared to n log n at the expense of making the query twice as expensive if you want but it's still a constant and a small constant instead of returning just one entry from an array we take two entries from a table and compare the array entries that's still uh very efficient

9:00 i haven't talked about the preprocessing so far this was just how to solve the queries if we already have this 2d array m prime computed for us if if you think about it the preprocessing is very similar to before we can reuse the information that we've already computed to speed up the process the the precomputation if we would do it naively so maybe this is worth writing down if we would do it naively

9:37 we're essentially still paying a linear cost for some of the entries so uh if we would just find the minimum in each step we would have n times the size of the table and that's still quadratic and actually a bit a bit more it's not as bad as the cubic that we've had before but it's also not quite what we want

10:01 but we can do it smarter by exploiting again the struct the recursive structure of arrangement queries if i have a range i up to i plus 2 to the k

10:17 then i can always chop that up into two halves so there's a first half and a second half and these are actually already computed because this one goes from i 2 i plus 2 to the k minus 1 minus 1. so that is just m prime of i and k minus 1. and the second range similarly is m prime of i plus 2 to the k minus 1 and then k minus 1.

10:59 so i can do the same trick that i do in the query instead of pre recomputing the minimum in the large black range from scratch i can use that i've already computed the minima in in these two smaller ranges and then the minimum and the big one is either the minimum of that range or the minimum of that range and i can find out which one it is in constant time so we've used the same trick twice both in pre-processing and in answering queries if you have a big range you can decompose it into two parts if they're touching or overlapping the important part is they have to cover the entire range and you've already computed the minima in these ranges you can just take those minima and compare them instead of the entire range that will be the key technique to speed up arrangement queries also in the more sophisticated solutions that we'll cover next but it's it's important that you understand this part here in the sparse table solution where it is still fairly nice and clean the two sub-ranges are always a power of two hence you've already computed it for the pre-processing part we just have to make sure that we compute things in the right order so going from the small ranges to the big

12:19 ones that was the same in the in the last part the pre-compute all solution also needs for this uh n squared pre-processing time you also need to compute the solutions in the right order but that's that's easy to do and with that we get an n log n preprocessing time constant query time solution