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

0:02 in the next section we'll look at a few relatively Simple Solutions for this problem they will not achieve the optimal pre-processing and query time yet uh but there are building blocks that we'll use and also it's uh they're much easier to understand so we'll start with those uh first a few trivial things you can do very easy uh showing the extremes of of the scale one option is you do nothing at pre-processing time um which means at query time you have to do all the work um all the work means well we have to find the minimum in some range so we just walk through and keep track of the current smallest element uh if we do that say from from right to left we can keep track of the last occurrence that's the leftmost um different options and then you need time proportional to the length of the range that you're looking at but in the worst case the range that you're looking at is the entire array I can always query with one and N or zero and N minus one uh and then the query time or the worst case is linear and that's not not particularly useful uh that's too slow but it's an option right and we have no no

1:24 pre-processing time I could basically have said zero but order one is upper bound is of course also true The Other Extreme end is we do all the possible work at preprocessing time and at query time we just read off the stored result how would that look like uh I can store a 2d array M for minimum which just stores in m j it stores the answer to rmq IJ and then the query is is trivial query just says return rmq J uh return m j but the pre-processing is super slow now if I do it really stupidly I could say for I from Zer to

2:22 n and then for J from uh I guess it can't start before I okay we can we can have the same um now I have to compute the minimum so uh we could say let's let's spell this out doesn't

3:00 then I probably want to remember the position for from I to J and if my previous minimum is no longer the minimum so if I compare it with AK and AK is strictly smaller then I update my my entry a that would be one easy solution I have to store this okay gets a bit running out of space

3:51 here that would be simple code to compute all the values MJ up front and this takes cubic time because I have one Loop that takes any durations another loop that takes n iterations and then the third Loop in the middle that in the worst case takes length uh n and uh you can again prove that ASM totically it's it's cubic can you do better somehow speed that code up a

4:26 bit you can massively speed it up in this inner loop because we really um really throwing away all the knowledge from past rounds if you iterate over um the sub problems in a slightly smarter way then um how do you get from Mi i j to m i j + one for example so I make the range one bigger at the right end now if that's my previous range that's the new element i j j + one in the range from I to J there's some minimum somewhere now if I add one more element at the end there's two options for the minimum of the new entire range it could either be here or it can be this element but it cannot be any of the other elements because these were already bigger than that element so I can make the next bigger range and find its minimum in constant Time by just comparing these two options right so that's how we get uh the running time down to quadratic again which is now the size of this array M and we have to at least fill that so there's no way around it um maybe it's worth spelling out some code for that so all we have to do is make sure we iterate over M by order of the length

6:09 of the of the range so we can have anything between one and N elements then we iterate over the range it can start at zero any anywhere up to n minus

6:39 L and then um I guess we can go do a case distinction if the range is just one then I'll store at I Mi I I + L I'll store I that's the index of the minimum if I just have a single

7:08 element and otherwise there's a smaller one so I can take my I and I + L minus one we'll use that a few times let me give that a name

7:36 so editing the code on this on the Fly is maybe a dangerous so one option is this the other option is J + one I have two positions that I have to check the position of the previous minimum and the new position that I'm adding into into the range and so again running out of space

8:00 let's move it a bit up here okay I can cheat a little bit so I'm checking now if a of a is less than equal a of B then I keep

8:44 okay so with this code we can solve all the pre-processing in quadratic time so I have two Loops this one runs end times this one runs end times and everything I do inside of here is is constant time it's just a fixed number of instructions okay by assuming out again that gives us uh order n squar pre-processing time and then constant query time so the constant query time is great but we're wasting a lot of space and because we have to fill the table even if we're smart about Computing the next minimum we still have to write to the output so we won't be able to improve upon this N squared running time for pre-processing unless we don't store as much as much

9:33 data okay how can we store less the idea is to do what we've done in the trivial pre-processing everything step but don't remember as much actually remember very very few of the entries uh and what works here is only remember entries where the range that we cover has a length that's a power of a two of power of two okay um first of all immediately from that uh we can bound the number of entries in table because the overall length of the range is never more than n so there's never more than log n powers of two below n and so we have for each starting point at most log n entries which is much smaller than n squ and uh it's convenient to store those instead of giving the start and end index which just give the start index and then the power of two or the length then you have it back in a nice contigous piece of of

10:51 memory now that's fine suppose we can store we can compute those answers and store them how is that helpful for queries we can no longer just return M of I and J on my might not have stored the answer right luckily I can still reconstruct the answer I cannot immediately output the answer but I can reconstruct the answer in constant time and the reason for that is as follows uh no matter how long your actual query range is in this case it goes from five to 18 so I guess it's uh is what 14 elements um that's not a power of two right so I don't have an entry in my table that directly tells me for this range where is the minimum but what I always have is a value K that's um well

11:42 uh a value K so that 2 to the K is between the length of my query and half of that that always exists by the def by definition and so I can cover my red range by by two r ranges that have power of two as length and it's always so that they at least touch or actually they always overlap by one because we're I could have made this strictly less okay the the range is definitely at least touch so they cover the entire red range and so um where's the minimum in the in the whole red range well we don't know but if there's a minimum in the blue range here and a minimum in the the green range there it has to be one of the two if it was any other element then there's a range where they are together with that element and the answer in that range contradicts for example I mean the 10 is definitely not the minimum I should have circled the real minimum which are marked by the arrows sorry that was more confusing than helpful maybe uh why can this element never be a minimum well if it was then it would have had to be the minimum also in the green range but rmq for the green range

13:07 said no here here's the minimum so the overall uh rmq in the range from one from I to J from 5 to 18 is one of those two positions whichever gives the smaller value again with ties broken to the left as before so I asked these two subqueries which have a length of power of two so these are these are just

13:44 stored so okay I don't know if I can fit that here that one's stored in in M Prime ik and the green one's stored in M Prime J - 2 the k + 1 a bit less uh nice but still it's just um some number that you can compute so these two elements you can look up that's two indices in the array maybe 10 and 17 and then you do this this check you uh find the ele find the values in a do one comparison so this notation Min just means the position where the minimum is attained among those two options so you would have code that's like this if a of a is less than a of B then the result is a otherwise it's

14:54 B so that's how you get by with just n log n entries instead of n s the pre-processing can be done similarly to what we've done for the stupid version where you compute all answers because if you go from a range I plus I up to I + 2 the K minus

15:22 1 and now you want to go to that with the next largest range so the the power of two one big what does that look like this is one range and then you have another one of the same length and that gives you that that range so you have the same situation as here you have a blue cover a blue part on the left and you have a green part on the left on the right the minimum of the entire range has to be an element from somewhere in the range so it's either the minimum of the blue part or the minimum of the green part and both of these you have computed because they again have a power of L power of two as length so you can do um with uh a similar similar trick you you look up the smaller ones compare which is smaller and that gives you the result for the long range so as before you can fill each entry in our table in constant time so the overall pre-processing time is n logn for the size of the table and query time is still constant it's a different constant it's slightly slower than before we can't just look up one entry in an array instead we have to

16:35 look up two entries in an array and do one comparison but still constant time okay so far so good that's as about as uh as about as far as you get with simple tricks like this so you can try to think about how to make further um further improvements um but I'm not aware of a solution that gets there if you're if you're just trying to do that approach somehow get rid of even more elements it doesn't seem to work so instead uh you need some fundamental different approach to solving that problem