Video 7-3: Cartesian trees

0:03 And for showing you how you can do better, we need to work out what the combinatorial structure of this rangement query problem is. And it turns out that there's a a lovely even bjective uh structure that corresponds to this problem. Uh for that, let me uh first draw this is just an array where the numbers are drawn as poles. The higher the thing, the bigger the number. And then you can visually think about range queries as picking a certain range in the horizontal direction and then uh let a a line fall down from plus infinity until it hits one of the poles. Now to make the pictures nicer here I'm using max queries instead of min uh just because it is nicer to draw poles of positive height. Of course, you can always flip all the com comparisons around and make max into min or min into max as long as you need just one of the two. It doesn't matter which one you solve, you can always negate and get the other. But here, just to make the p pictures nicer, everything's a range max now. Okay.

1:15 Uh then again, so the the picture is you you take this bar and let it fall down until it hits the first pole. And that's your maximum obviously and the position where it hits that is the range max same same definition just explained visually. Now how does that uh how does that get a combinatorial structure? We could build a tree by taking the entire range over the entire array. So initially I'm gonna kill this pen eventually. Ah it still works. [snorts] So you let a line covering the entire array sink down until it hits the first pole. And uh imagine it's a brutal pole. It just cuts the uh line in half. And so now the two left and right parts can sink individually down independently of each other. So this one will indeed sink all the way down to this uh pole whereas the other one will stop earlier. Okay, whenever they hit a pole they become split and independently keep falling down.

2:29 Also uh whenever I do this I have a single first hit pole on the left and one on the right. Again tiebreaking take the leftmost if there's several. And these we connect to the previous uh whole array maximum with child links. So that's going to be the root of a binary tree with these two children. And uh I can recurse in that this line here it used to be you know from here to here. Now these are two independent lines that again sink down between these two tall poles. And so they keep going and I get more and more nodes until this is the final picture. Okay. Uh the way the way to get get the tree is top down is uh the direction and then you recurse on left and right whenever you have a maximum.

3:26 That's a cute tree. What does that have to do with range maxima though? Uh if you look at a range like our red range here, there's going to be a leftmost and rightmost note maybe in red in the range that's going to be these two. Now the range maximum is the lowest common ancestor of those two uh nodes in the tree. If you walk from those up to the root, at the very least at the root, they have to join paths. And uh they usually join a bit earlier. In this case here and that note uh this is again uh the way I draw the trees here. The root has to be between those two. One way to see that is I've put the indices in the notes here from left to right. These are the indices of the array. Uh then the tree we built happens to be binary search tree ordered. All the numbers on the left of a node are smaller than all the numbers all the or smaller than the number in the node and smaller than all the numbers to the right. As in a binary search tree, it's obviously by construction because we just split in the middle. So you could also say these numbers in here are exactly the uh array indices or the in order index in the tree.

4:58 If you do an inorder traversal of this binary tree uh whenever you see a when you visit a node you mark it and increment a counter then you get the same numbers. [snorts] Okay. Then uh the lowest common ancestor where the paths to these two uh nodes split for the first time has to be between those because that's a point in the binary search tree. Think about it. It was a point where we decided that six is smaller than nine but 14 is bigger. As long as they're on the same side, the paths don't don't branch out.

5:33 Okay, maybe uh uh that's uh helping to to visualize this a bit. So we've reduced the problem of range max queries to finding lowest common ancestors in binary trees.

5:51 That may be useful or not. Uh the way how we will use it the way why it's useful for us is primarily that since this is all about the tree, we don't need to know the heights of these poles anymore. All that counts is the topology of the tree. how many uh well what what nodes are are there what are left and right children. We don't need the uh information of the numbers. And that's useful because there's fewer ways to build trees than to arrange numbers. Here's a slido question where um your task was to find where the minimum in this range lies. And there's going to be an array that tells you by numbers. But we can figure this out from the tree. Since we're such a small group, maybe we don't need the slido question and you can just quickly work it out.

6:58 volunteers. Now remember we start counting at zero. First we need the in order traversal of the tree to mark the nodes with their index with these numbers because otherwise I don't know what one and five means. in order traversal starts at the root then goes left as long as it can and as when that's no longer possible when you return then you visit the current node then you go recursively right so I'm going left left then I can no longer go left so I come back and this guy is the first one I visit so that gets zero right then I'm done with this sub tree because right is empty so I go back up now I'm done with left for this guy now I visit this node mode gets the one. Now I'm going right and then again I'm going trying to go left as long as I can but there's nothing. So I come back and then I'm at this node. I visit it so it gets the next number. Uh and so on and so forth. Okay. The way I drew the trees, you could also say it's a sweep line from left to right. Whenever you hit the notes, they get the next number.

8:12 But this is because I drew them in the sensible way you should draw binary search trees. Okay. So we can identify the two nodes we're talking about one and five. Uh in this chapter I made the the end points inclusive for no good reason other than um lack of interest to change the pictures. So where's the range max?

8:42 What do we have to do for these two? We have to find the lowest common ancestor which of course you can do by walking up and seeing where the paths uh meet. So that's the guy at index three. Okay, good. Uh here's one way how this array could look like that gives the same uh range max position. Um there we go. Now, how is this useful for our data structure? As I said before, we don't care about the actual values, just the tree counts. So, let's count the trees um and see how many different ways range max queries can look like. The good thing here is I didn't I didn't stress this um carefully enough, is really a bjection. If all you know about your array are the range max answers for all possible ranges, you can still reconstruct the cartisian tree. And if you have the cartisian tree, you can still reconstruct all the range maxes by definition because they're uh given in the tree by the lowest common ancestors. So the two are exactly equivalent.

10:00 knowing all answers of rangemax queries or knowing the cartigian tree of an array. Uh that also means I can count binary trees to count how many different options I have to answer range max queries.

10:18 For example, here um is my my small tree and it has was it eight eight nodes. There's only a certain number of different trees with eight nodes that could be a a cartisian tree and the precise answer are the Catalan numbers. If you have nodes and you want to build a binary tree then uh that's the precise answer how many you get. For example, if you said n2 then there's uh five options. There's this tree, this tree, there's a lopsided one, the symmetric one, and the balanced one. And hopefully if you insert three, this works out. So it's 1 over 4 and then 6 choose 3, otherwise known as 6 factorial over 3 factorial, 3 factorial, and the four. So uh you have the the six factorial six 6 * 5 * 4. There's only the six * 5 left.

11:32 The rest is canceled with a four and one of the three factorials. And then there's another three factorial which nicely works out to six. So the answer is five. Okay.

11:44 Now, that's um if we were doing an intro to combinotaurics class, we'd dwell more on this and how to compute it, but we don't actually care. All I want is an upper bound for the number of different trees. And this one's far easier to prove. One example um well one way to prove that there's no more than two to the 2n trees of that shape binary trees is by giving an encoding for the trees using two n bits if that's possible and I can uniquely reconstruct the trees then there can't be more trees than 2 to the 2n and one way to do that is for example to say I'm going to write for every node in a depth first traversal Has it got a left child? Yes. No. Does it have a right child? Yes. No. So that's one option. Um there's many many others that are similar or slightly more useful for some purposes, but this is good enough.

13:03 I guess um I should say a pre-order traversal that we have a clearly defined visiting order of the vertices that clearly uses two bits per vertex. And uh if two trees differ, they have to differ at some point in the child links. What's less obvious maybe is that you can reconstruct the tree uniquely. But that's why it is important that you do a pre-order traversal because then you can always keep track of which nodes still have open uh edge slots that we promised will be filled with children but haven't yet. And then because it's pre-order de for search, you know which one is the next one.

14:02 With that knowledge that if we have n numbers there's only 2 to the 2n a few less options for how the range max arrangement queries can look like. We can uh come back to our uh previous approach of taking a big array and breaking it into small blocks using sparse tables for the minima of the blocks and then doing something else for uh queries within one block. That's the intra block queries.

14:38 we'll have to be a little more uh restrictive with the block size than previously. Before I just said big O of login is sufficient. Now I need to fix the constant. If I put it for example at at a quarter then 2 to the 2B the number of cartisian trees or the upper bound is just square root n.

15:01 So I've picked my blocks with this B so small that there's only square root N different ways how all the possible range queries inside this block can look like because there's only so many such binary trees which means there's going to be among all those n divided login blocks that we have of our array there's going to be a lot of blocks that do the same they have the same local answers of course for different values and shifted in index But if you locally look just at this block, they're identical. They're equivalent in terms of all range queries. And so we can use exhaustive tabulation, which you guys already know from uh the alignment chapter.

15:48 We're doing exhaustive tabulation on these small blocks. We write down the type and then do an exhaustive table of all the types and all their queries. So for every possible tiny little cartisian tree, we're just premputing the stupid way all n squ or b squ uh rangeman query answers. That's going to be a bit wasteful, but because b is so small, we don't care. And then on top of that, we just write down for every block which type it has.

16:27 Now the uh extra trick why we can do this as a data structure is that we make sure these types are just numbers or bit strings. It's the same for a computer. So we can use them as an index in in an array as a kind of quick way constant time way to jump to the right type.

16:53 Okay. Uh how to compute this in the pre-processing is also not hard. You can do any representation of a cartigian tree using 2B bits. For example, the one I've shown you. Um it's as long as it's just a code, that's good enough. And then we also fill going through all possible trees. Say we have our little little tree like this. Now I would have to write this down in binary, but uh let's spare us the details or might as well do it. Okay, this has no left but one right. This has one right left but no right and this has nothing. So that's going to be the same. And then I have uh re choose two different range queries not so many. I could ask between zero and one that's these two nodes. Where's the minimum? Well this guy is on top. So the answer will be zero. If I ask uh for zero and two say and the same same uh block type I also get zero. If I ask for one and two I get two. Okay. So you can imagine if we fill this for all possible trees of that small size and for all possible I and J and we write down the answer.

18:13 How much gonna how much is this going to take us to do the square root n block types because B is so small B square combinations at most. So in still very very little O of N time and space we can fill this table.

18:36 And with that we found a solution for arrangement queries that at least in theory is perfect. There's nothing left really uh to say if you're looking at big O. It has linear time pre-processing time which you're going to have to look at the array at some point and constant time for the queries where we do this decomposition in interblock and intra block queries and for the green ones the in intrablock queries uh we use this table lookup.

19:09 By the way, this is also the how you solve lowest common longest common extensions in in strings where we used back then uh for for tandem repeats etc. there was there was this thing left open right okay so essentially best possible in terms of these times it's a bit more complicated then maybe you want to implement it turns out this exhaustive tabulation technique is really bad in practice because uh to make it feasible to really have the space to write down this exhaustive table you cannot afford big blocks they're really tiny like uh uh it depends how much really you have to to store but maybe a dozen or so is already the limit. Uh and then the rest is still this this dividing by 12 or so in theory is login in practice is uh is not such a big speed up. So often times people um choose slightly different implementations that have in theory a worse running time asmtoically but uh tend to work better on current machines. But that aside, um the theory problems totally solved and uh we can finally close this black box from last time.