Video 7-2: RMQ via sparse tables

0:03 The first non-trivial solution for the arrangement query problem is called the sparse table solution. And this is essentially very close to the premputee all possible answers except that you try not to premputee most. Um you only keep a certain carefully chosen subset of the queries. chosen in a way that you can solve the others by puzzling together from the ones that you do save what the answer is. What do I mean by that? Um, one specific way to do it is to only save premputee the answer for queries where the length of the range is a power of two. So we'll have uh this parameter l the length of the range in the array that we look at and assume that's um 2 to the k. Then uh first of all you can store those answers using k as an index instead of j and also more crucially the number of things you premputee is only n login and all possible starting points but then for each starting point only the logarithmically many ranges of sizes power of two.

1:14 Now that's fine if your query has indeed um a length power of two. You're happy you have the solution. What what if you do for all the others then you can't directly answer the query but you can still figure out the answer in constant time namely whatever the length of the query doesn't matter there's always going to be a power of two that's just below but more than half and so you find two overlapping or touching ranges I guess they're always exact have to be overlapping otherwise as there would be one that covers the whole thing. Uh but doesn't matter actually. There's two ranges that together cover the query range. And so you'll get a minimum from the blue and from the green part. And certainly the minimum of the entire thing can be one of those two positions, but nothing else. Uh then you have to be a bit careful again with giving the leftmost priority and all that. But let's uh let's not be uh too strict about that. Essentially the problem is solved. We find two positions from looking up the queries of powers of two size and comparing the values there in the array.

2:29 And then we know in this case ah one is smaller than two. This is the answer for the query. So to write it shortly and uh ignore the type breaking I guess uh assuming argument is doing the right right type breaking I just have to compare two values from the array.

2:57 How good is this? Uh I'm using n login entries so I have to compute those at the very at the very least but query time is constant. It turns out you can also compute every entry in this table in constant time if you do it in the right order. Namely, you go from small to long ranges. Then the next next longer range consists exactly of two of half the size. So you do precisely the same trick as here to get the minimum of a new range that's double the previous two. There's going to be two that cover it. uh and then there's the range min that you've computed iteratively before you find the minimum of those two. That's going to be the minimum of the entire range. So in constant time for each entry you can compute this which means the pre-processing time is n login. That's the first solution that's somewhat usable. Uh it still doesn't solve our original problem. We wanted linear time. Uh but at least this is way better than the trivial solutions.

4:03 Uh and indeed at this point if you've seen enough of these examples you may wonder if a simple trick is good enough to reduce from n login to n by just applying this this technique on a subsampled input.

4:22 And that indeed works. Uh gives you a slightly different um trade-off. If you take somehow a cleverly constructed input that has n divided login elements then n login turns into linear time. Okay, that's easy. How can you use this here? One option is you break the array up into blocks of roughly login numbers. Then you take the minimum of each of the blocks and that's the uh array that you feed into the previous solution with the n login pre-processing time constant query time. So um you can find if uh your queries are kind of rounded to block boundaries you can solve the rangement queries because you've found the smallest in each block. So any range that precisely covers an entire block will have to have as answer one of these blue uh positions. Uh the only thing you can't immediately do is some range that uh doesn't align with block boundaries.

5:42 But that's uh the last thing for today. If you have a general query, you can still do something. namely there's a part in the middle that has entire blocks and that we already know how to solve. Yeah. And for the other ones, okay, that's bad. But, uh, at the very least, I could just scan them and find the minimum their brute force. So if I do that um if I do that after I found the minimum of the green guys there's three possible values that I have to check. The overall minimum in the query could be this guy or could be the best of these or could be the best in here. And that's it. Um, so far we've covered how this works and the intra block queries I could do in logarithmic time because that's the size of the blocks. So in in total what we've seen so far would be linear prop pre-processing time and logarithmic query time.

6:48 That's again not what we wanted, but it's another reasonable solution that's quite easy to to get and maybe a a reasonable alternative to the things to come. But I'll leave it there. And how to get this down to constant we'll do next time.