Video 9-6: §9.5 Four Russians lookup table

0:00 Introduction

0:03 in this last subsection of this unit and actually the last subsection of our of our module i want to show you um a trick that uses the facts we learned about the cartesian trees to finally get to this optimal pre-processing time and space data structure for range minimum queries and that uses the so called for russian trick and at that point i want to include a little disclaimer or a little uh well rectification if you want it's about an algorithmic technique that was published in in a two-page paper in the seventies in russian by uh alexander of denitz

0:46 i'm probably not pronouncing them correctly but i tried and they all worked in moscow at the time but as far as i know two of them are russian and the others at least then it's is uh israeli he might have been russian at the time i'm not sure and i didn't find information about the last one barajev it's just not clear if they are russians and unfortunately american authors ignoring that fact use this method of four russians never the nevertheless and uh not giving them the honor of mentioning their name is worth enough but it's also factually wrong because it's probably not for russians unfortunately the name it got stuck because it was coined at the time when well 70s you remember what what happened in history at the time it's not relevant for algorithms now but this name is not great but it's in so wide use now that people kind of gave in and kept using it i wanted to give this this little credit to the original authors nevertheless without just mentioning their nationality or their place of of work at the time

2:00 Simple solution

2:04 okay first step in in this solution in this this more sophisticated solution for the arrangement problem is taking what we have and see what we can get with simple tricks uh ignore the picture down there for a moment what we've seen is the sparse table solution is an n login time and space preprocessing solution that gives you constant query time but the n log n is is not quite as good as we wanted however if we apply it to a smaller subproblem one that has only n divided login elements so we apply it to an array of only m elements where m is chosen like that then m log m the log n cancels so that's linear then so we can apply this uh the simple solution even though it's not it's sub-optimal we can apply it if we just make our input a tiny tad shorter a log n factor smaller we've seen that trick before in unit 3 when we're talking about parallel processing here we'll apply a similar trick but to use it in a different way so the first step is we break our array a into blocks of little b elements and that number is is carefully chosen it will not make sense at this point why exactly it's log

3:26 n over four it will make sense in a couple of slides uh for now what we do is we just break this array into blocks likes like so um and for simplicity i i'll assume that there is no leftover block at the end but that's a minor detail that you can handle if you want or you fill your array with elements that are if it's range min bigger than all the others so they never come out as the arrangement so that's what you do and that breaking a into blocks is only conceptual um but uh we can we can imagine that it's really consists of little blocks here it's it's eight elements each in our example b is eight but in general it should be chosen like this and now from every of these blocks you nominate the smallest element and promote it to this small blue array the b array to be precise uh we don't take the actual value there instead we take the offset inside the block so in blue here i noted what is the offset inside the block and if we know the block id so 0 one so maybe this is uh worth pointing out so that's block zero right maybe obvious but uh let me write it down

4:51 log one block two etc up to block m minus 1. if we know the block we can take that number and multiply with b so that gives us the the first position then we can add the block local offset that's the little blue number here so our array b stores for block 0 what is the offset inside the block of the minimum in that block so the blue guy is always the smallest elements only inside of this block okay if you want this is a little range arrangement query in itself where we exactly specify one block

5:37 why do we do this because b now has exactly the size that's small enough so that we can use the sparse table on it without spoiling the overall pre-processing time or the overall space b is chosen or the block size is chosen exactly so that you can take this array b it's not too long it's shorter by a login factor so you can apply the sparse table technique on it and we're still within our desired linear preprocessing time and well hopefully constant query time we can do in constant time arrangement queries on this b array it might just not make too much sense why you want to do this at this stage but we'll come to that on the next slide

6:22 Rangeman query

6:35 query that covers a certain range i to j i drew this here in red and remember we imagine that our array is broken into blocks like so how can we make use of the fact that we can use rangeman queries on b to answer this query well first of all notice that any such actually covers three ranges there's a certain part here so this this is this um this prefix i don't want to use blue for that uh so here's the prefix of that block that's covered here's the pre as suffix sorry that's the suffix and here's a prefix of that block that is covered

7:26 so we have a part of a block at the end of the query at the beginning and at the end but then in the middle we have a range of blocks right so for all but the leftmost and rightmost block we know that we cover entire blocks and that is useful because we can use um we can find the range minimum in this blue part using only the b array because any range minimum in this in this range will be one of these three it can only be a range minimum of a block that becomes the minimum of a larger a range of blocks okay it's a lot of ranges i know uh that's why i warned you up front so what we do is we divide the query into a constant number of other queries remember this is very similar to what we did for sparse tables but here we have to be a little smarter in how to do it we have one large range that scans entire blocks that's this blue part and then we have two little leftovers but these are only inside a single block so i'll call these intra block queries inside the block and inter block queries with the spanning blocks okay

8:56 and now the fun thing happens again if we ask what is the result of the red arrangement query the entire range it can only be one of a few isolated points it can be the minimum in the green range in this in this suffix of a block or it can be the minimum in the prefix of a block or it can be the minimum from the blue range now the example here is a bit misleading i would have liked to have this minimum outside so let's suppose this is not here but instead is here what i want to stress here is the minimum of this green range need not be a block minimum and the same for this one whereas for the blue ones we spend the entire block so it can only ever be a block minimum

9:57 now what is more precisely what are the three ranges we can express that using other range minimum expressions so in particular uh this first one is that first arrangement query it only looks inside this block l l is defined here so you can just compute that from the the query index so we look inside one block and within that block we have a certain range that we span that's the the green part here we have the second green part down there it's the same thing just in a different block and we're slightly different slightly different indices and then we have the the blue part and that one's it looks a bit more complicated but that's only because this array stores the block local offset and not the actual index so we take the block offset um that is uh this expression and then we add the offset from the block where we find it so this is um you have to work out this in in detail um so that it makes sense uh this is the block local offset this is which block um turned out to be the minimum so that gives you the block id maybe this is a good annotation at this point

11:38 and from those two things together you can compute the candidate minimum from the blue range okay so it's it's not necessarily important that you follow the nitty-gritty details of how the indices are chosen um the important thing here is that you can take your query the red range again and you can represent it as three different queries and then the minimum of the entire red range is whatever gives the smallest value from these three candidates so that can be done in constant time if we are able to

12:22 find these three candidates quickly so that's what's stressed here if we can compute inter-block queries and intra block queries then we can compute these red ones and we only need constant time for that we compute the candidates if that's done we have a set of three possible positions in a so we just look up into a what is the smaller one and we return that index and indeed the blue range we've already solved that was the previous slide where we discussed that this b is actually small enough so that we can just use sparse tables on it so that's done the only thing that's left is the intra block queries so we've reduced the entire problem arrangement queries on the full array we've reduced that now to only solving the little sub problems in a tiny range just log in elements at most it turns out that is the tough part though and you have to apply a trick to get these so the intra block queries remain and we want this time overall the challenge is that we have almost as many blocks so we can really only spend log in time per block and we can all also just spend log in space per block and we have to be um really careful with

13:51 that whereas if we uh wanted to store the cartesian tree in a in a way that it's easy to um well you it does it doesn't seem possible in an easy way to store the cartesian tree so that you can find the uh the lca efficiently

14:17 and the trick is we don't have to so we have many many blocks but they're all fairly short just b numbers we can also we also know that we can encode the cartesian tree for such a small range using 2b bits and we've counted that the number of different cartesian trees is not that big so if we insert what we know about b in here and compute we find there's only root and different cartesian trees even though we have almost n blocks in total so we have n cartesian trees in total to store but only root n are different possibilities exist so that means many of these cartesian trees are actually identical they look exactly the same

15:09 so how can we make um make use of that and that is what the for russian technique comes down to we take each subproblem and represent it by its type so that's a local encoding of the of the cartesian tree in our case and we will use this two-bit encoding that i'll i've shown you then we enumerate all possible sub-problem types they're just root n of those so we can just pre-compute them all and store them in a big table and then use the type as a lookup as an index in that big table so that's in a sense instead of figuring out a smart way how to solve these many instances we just solve a problem that's simpler because there's few different cartesian trees in total there are not so many to choose from so we can afford to just pre-compute them all and let's briefly see how this is done the preprocessing does um two steps the first one is for every block we compute the encoding of the cartesian tree that is easy to do in linear time i don't have time in the lecture to show it but it's actually fairly simple to do it there's a stack based algorithm to compute the cartesian tree and then a traversal of the tree gives you the

16:05 Preprocessing

16:32 encoding we manually simulated that and then you you use these codes um and store them so you have an array for each block you store the code in the cartesian tree and the second big thing you do is you store one big lookup table where you have um an entry for each block type so suppose um there's one entry supposedly that b is four then we have one entry for this tree we already know the block type for this tree was three ones and five zeros that happens to be the encoding of that tree remember the the clicker question and then we can we have entries for all possible rnq queries that are possible inside this uh inside this tree so there are actually not so many in this case i think this should be all and we can just look up what the numbers are so this is 0 1 2 3. the arrangement between 1 0 and 1 1 is higher so this is 1. zero two it's two zero three it's two because that's that's the root one two two is the root whenever two is contained it's it's the answer so it's uh it's two in almost all cases that's a fairly boring little example but that's how it works and you fill this table for all possible

18:04 trees of b nodes you just pre-compute them all and store this in one giant array okay now this is good enough because the number of block types the number of different entries in the first column is only square root n that's what we just computed the number of combinations of these columns i and j is b squared and that's that's log n roughly so we have uh square root n times log squared different rows and that's a fairly small number um even if i don't know if n is a million this is a few thousand so this is this is uh not very big and we can also compute this efficiently so with those two steps together we bring down the overall pre-processing time to linear time by uh instead of working out how to solve these small instances really we do an exhaustive lookup table using the fact that there's only few different types all these little instances of the problem can only be one out of square root n different shapes and so we can afford to to pre-compute them all and thereby circumvent the fact that just given the cartesian tree it's fairly hard to find lowest common ancestors efficiently but if you have this lookup table it's just a lookup it's just um an access in one big array

19:45 Conclusion

19:49 and putting that all together i might have lost you in the process but this is all the ingredients that you need to create a linear time pre-processing linear space constant time query data structure for arrangement queries and with that we've also solved the lce problem in the same space that was the last big open problem we left in unit 6. so with that we've brought the module to a nice conclusion where you've looked into all the black boxes that we used and they seemed magic at the time but now you can really look into this and understand the details it is a bit complicated i agree also to implement it there's there's tricks where you can simplify it a bit and compromise on the theoretical guarantees but the theoretical guarantees are best possible and this is is also a fairly recent result that i like very much

20:55 there's some open problems in this area where research is still ongoing in particular about getting the space usage to the absolute minimum or and or avoiding to have access to the array at query time so a nice little twist on the problem is that you get the array at pre-processing time but then i'll take the array the array away from you and for the queries you have to work only with your data structure and you get no no further support no you cannot look at the array anymore