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

0:03 in the next section we'll look at some of the more Immediate Solutions for the rmq problem and we'll see that these are actually building blocks we need later on for the sophisticated version it will be again in a way uh the final solution will not be some uh genius insight and then the rest just Falls in place it will be a cool technique but then building on the simpler things that we discussed first and I don't know if you've spotted this pattern uh that happened in other places too so it's maybe also a way to advertise for always try the simple things first put down what you can easily achieve and see how far that gets you um and then you have a repertoire to come back to

0:54 okay I'll make this more concrete but Let's do let's do the very very simple things first uh it's a problem where we have something at pre-processing time something a query time let's let's etch out the extreme cases first we can either do nothing at pre-processing time right then all we have to all we have left at query time is to just go through the array and find the smallest element so that's a linear scan of this of this range you just go through find the minimum you all know how to code that by now I guess um so that's that's not hard to do but of course the query in the in the worst case is the entire array or almost the entire array and then you need linear time for the queries but you could even say you you spend zero time at pre-processing but let's be generous and call that constant time just returning okay that's not too useful because um uh the queries are very slow uh The Other Extreme is I don't want to spend any thought on the query time on the query side I can't do that if I have pre-computed all answers so this is not completely out of the question you could have a big array a two-dimensional array for all

2:18 positions I and J it can be a triangular Matrix we only need it for I less than J but that's just a factor of two so that won't won't save us much so we store in this array um all the possible Arrangement queries up front we do everything at pre-processing time then the the time to answer a query is just finding the position in the array that's constant time then but the query time is really slow if you do it the naive way you would have for I from 1 to n for J from I to n so a double Loop and then inside the loop you do a scan like this and so um in terms of the big Theta class that's that's cubic that's very very slow

3:09 you can very slightly improve this uh to quadratic time instead where essentially you compute each of these values in constant time now and the the reason why you can do this is a is a simple observation but I think it's worth stating that suppose you have some some range I the J if you if you're smart about the order in which you compute the answers you could say okay that's that range is some range with one more element so I look up hopefully I have computed that first the range that ends one element early and now there's really two options for the minimum of the entire range the minimum can either be the new element or it's the old element the old minimum in the in the left so it can be the Min in here or this one so I have I have one comparison to make I'll look up where the minimum is in the in the I up to J minus 1 range pick out that element and compare it to this new one new last element and whatever is smaller wins and gets uh the entry of that of that next entry

4:27 and that way you only spend constant time for each element to fill that's better uh but still a long way away from linear time and I think this is um this is all you can do with these uh very simple Solutions

4:48 now if you think about this a bit um we kind of like this pre-compute all because it's very fast at query time but maybe there's an option to not store every single query because that not only costs us space it also costs us the time to compute the all the entries or even write the entries at least

5:11 and so that's what the the sparse tables um do effectively they they have another observation about the nature of this problem that allows you to reduce what you store a bit more

5:26 we still have a such a two-dimensional uh Matrix but the meaning of the entries will be a bit different we only store this we only store an entry when the length of this range is a power of two okay like a shallow um superficial com uh comment whenever some always try powers of two first they often work but uh I mean there's um there's a reason in this case for that that I'll show you in a second uh but let's let's suppose we do that uh how how much does that help we still have all starting positions I but then we could say we don't have all uh right endpoints J we only keep those that give us a power of two because the range is is bounded by n there's only log n powers of 2 until you hit the end of the array

6:24 and so we have at most n log n entries that's much much fewer than than N squared and so if we want we can store that in a different Matrix I gave it a different name to be clear so it's m Prime and the meaning is as is defined here so it's it's m of I and then instead of J we have I plus 2 to the k okay so we're still storing the explicit results of some arrangement queries but only a small subset of them

7:02 but then how do you answer a query that's not at length of Power of Two and the trick here is that whatever your range is you can cover it with two ranges that have length Power of Two so that they at least meet in the middle or overlap a bit now why does that help you can independently look up the the blue range and the green range so the the power of two length range aligned left and aligned right in your range and you will find that there's two two answers from these those are the Minima in the ranges in the green and blue range

7:46 and the minimum of the entire range has to be one of the two it has to be one of the elements somewhere and every element either lies in the green range or in the blue range or maybe even in both

7:59 and so formally we can solve the rmq query in this case by taking whatever is smaller the minimum of the blue range of the minimum of the green range and these again are looked up in our in our M Prime table because we can pick them so that the length is a power of two

8:24 I guess I should fix this mistake here this uh a minus 1 because we count endpoints inclusive right the blue range is very easy you just start from I and add a power of two the green ranges you have to start with j and subtract right so you get this left and right aligned

8:54 and so yeah I guess the I don't know if I can squeeze that here the trick is that this is m r Prime I k and this one's M Prime of this lengthy thing j minus 2 to the K plus 1. and then K so both of these the red the green and the blue uh value can be looked up in our sparse table

9:27 I guess I should have said that's where the name comes from you're trying to store the original pre-compute all table but in the sparse way you only remember a small subset of the of the actual values and you forget all the rest turns out you can you can reconstruct them at runtime with just one more comparison all right

9:56 so that's the structure of the of the table we store we also have to pre-compute that at a pre-processing time but you can do this with the same trick as before if you're if you're trying to fill this table

10:16 what that means is a range that starts at I and exchange extends to the K plus positions well I can I can cut that range in half then I have two ranges of the next smaller Power of Two

10:37 and so you can you can again get that from from this we have to look up the values but other than that so we take M Prime I and K minus 1. that's this range

10:58 and the second range is is the one that starts later so it's I plus 2 to the K minus 1. then K minus 1. the minimum in the entire range has to either line the left or in the right half and this is the way to find out that way again in the pre-processing step you only spend the constant amount of effort for filling each entry and so the pre-processing time is is proportional to the size of this m Prime array

11:33 right so without too much complicated techniques we get this analog n pre-processing time constant query time question and find the thing whatever uh so the question was how can why can't why can't we simply search the array sure

12:03 right simply short there and find it rather than going to oh sorry all right sure uh well yeah yeah okay uh the game is that you're not allowed to modify the array and if you think about the I think it's an important point so uh this this may become clear here if you're if you're trying to find the the longest overlap between two of these suffixes if you were to take this array and just sort it you would completely lose the order and so I don't know you would have maybe all the zeros up front so you would you would get zero overlap between these so the connection is lost to what the array originally represented uh so this is only interesting if you're not allowed to modify the array uh in a sorted array I guess yeah the range minimum in any range is just the leftmost position right yeah but the the point here if you want uh something I didn't stress all that much uh you can pretend the ray the array is just read only for for what we're doing

13:31 okay so we got our pre-processing time and space down to n log n and that's where um if you've been doing data structures for a while you you may get curious this login Factor often can be removed with additional tricks and we've seen this over and over already in this module we've seen it for the parallel prefix sum for example we have the solution that had login span but then n log n work whereas the sequential algorithm had linear work and at the time we applied a blocking trick and could get away from from that and log n to linear in a way something similar works here too unfortunately it's it's more tricky because um there's still some problem left so the the solution will again use this sparse table solution as a black box on a smaller instance of the problem instead of doing it for the whole array of n numbers we'll do it for something like n divided log n numbers

14:42 but you still somehow have to solve the original problem and so that might not be so clear at first