Video 2-20: Lazy Search Tree Invariants

0:03 Uh, back to the lazy search trees. So, this is the bold statement, but it tells you not nothing about how this is done. Uh, the first part is essentially unchanged. That's what we've seen before. And that is fine as is. Um, I've also hinted at already that we have to do something within these gaps. And uh, we have to split them up into intervals of some sort. So, each of these objects here is essentially a secondary data structure that is, uh, maintaining a set of intervals. Uh, this one crucial property is that we have to bound the number of these Otherwise, insertions will get too expensive. Um, and, uh, in a way, the rest here is is not too, uh, exciting. You can take any balanced search tree to store these intervals within one gap. That's good enough to get log log delta log of that thing is the time to search for an interval within the gap.

1:10 So, delta can be at most N. That's where this log log N came from. Because insertions now have to go through the top part to find the right gap. That costs the right time for our lower bound, but then you also have to find the right interval within the gap. And that we cannot charge against an a lower bound. Um, and indeed, you can get away from it, but the way this is implemented here, it's another log log delta.

1:40 As before, the intervals themselves are, think of them as just unsorted linked lists. That's good enough. That's the overall structure, um, which is not at all new. Question? Is the tree this used very similar to those adding more ranks? It is similar to adding more ranks. Um, the difference is that these ranks up here, I think it's a good point to make, the ranks up here are queries. These are given by the user and we cannot choose which ones they are. >> [clears throat] >> The boundaries down here, I mean all of these are pivots in the quicksort sense. Right, each each vertical line here splits elements in smaller and larger. And that's the same here and here. But these ticks down here we get to choose. And we can also choose to forget some. We'll have to forget some eventually to keep the number of intervals bounded. And we can also make a deliberate choice which ones to pick. That's that's the difference.

2:38 And so I agree it feels the whole thing feels a bit artificial that you have this separation in two layers. Um and uh somehow one would wish that you could just have one big data structure that just contains these intervals and you don't need to have this secondary grouping. But maybe it's not possible so easily because these ranks are different from these in how free we are to choose them. At least um it's not known how to make this into one big data structure. It seems it seems not to work from what we've tried, but that doesn't mean it's not possible.

3:17 Uh so that that's the overall structure which shouldn't be very surprising from what I've told you before. The important thing will be how do we do this? How precisely do we choose the intervals? That's where um all the magic happens.

3:33 Uh and for that let me introduce a bit of notation again. So um I'm denoting these intervals by this I I J where this is uh the first index is the gap that this interval belongs to and J is just the uh sequential index within that gap and we'll freely use I I I J for a for an interval just as a a name. Uh where not always J will be clear from like a there's some J but uh you'll see. Uh answer the lists as before and they're split into left and right in the simple sense that uh an interval always sits somewhere within a gap.

4:25 And uh it could be that what is outside of it, this part and this part usually one of them is bigger. And so the smaller side where it's closer to the boundary of the gap uh it's getting very messy. This decides whether it's left or right. And if there's a tie, you make some tiebreaker rule. Doesn't doesn't affect much. So in this case this would be a right interval because it's closer to the right boundary. And in the sense that what is uh outside is smaller on the right than on the left. Okay? Um second what I already used is this term of the outside. So just to draw this again. Uh in the in the usual case if this is my interval number of elements on this side, that's my outside.

5:29 Uh the picture I've drawn is when this is the the the second part is the minimum. Um it could look the same on this on the left side. Intuitively what this outside means is my safety buffer away from the boundary of the gap. Uh this is for future queries. If a future query falls inside my interval, I have to pay to split that interval up. No way around it. And that's going to be a linear cost operation in the size of this interval. So, the idea will be to somehow I use the outside to quantify how much I'm allowed to spend. If I'm close to the boundary and the interval is big, then I'm potentially in trouble because a a query inside this interval may be very expensive for me to do, whereas the lower bound only goes up by a tiny bit. If, however, an interval is large, but there's a big buffer to the outside, I'm also allowed to pay more because the lower bound goes up by a linear amount.

6:34 That's why this is um a maybe natural thing to define. Uh and now come um the two rules that that govern lazy search trees. Number one is a a strict invariant on the number of intervals in each gap. That's what appeared on the slide before. Um the precise version is four times log of the total number of elements in a gap. And this is supposed to be a strict invariant true at all times, which means whenever it's violated, we have to do something.

7:09 It's only at risk of being violated when the number of gaps increases or the number of elements decreases. So, an insertion will never have to do anything here. An insertion can only make this looser. Uh but a query, because it splits one gap, um uh might might get into trouble there because now you may uh what previously was fine, maybe there were intervals here. This was fine because the overall int um gap was big. Now when you split here, suddenly these are too small for the new gap and you have to do something.

7:55 What can you do? Well, you just forget the pivot that separates them and thereby merge two intervals. Merge sounds like in merge sort, but that's not what is meant. It's just concatenation. In hindsight, we should have just called the thing concatenation, but I guess now it's too late. So, we I'll refer to it as merge, but remember it's just forgetting the pivot. It's just a metadata operation. You concatenate two linked lists.

8:25 Um The size of the intervals by contrast to this non-solution from before is not at all restricted. I'm not putting any hard limit on the size of any interval.

8:36 Just on the number. And whenever this is at risk to be violated, I'm applying the following slightly awkward rule, but that just seems to work. That when two intervals are located such that draw a case where this would happen. So, maybe these are the two intervals I I J and I I J plus one. And here's the outside of the two then this case the second. Uh I guess this is for the left. Um Let me cheat a bit and move this to the left side. And this as well. Okay, I can't really rescue this.

9:38 That's the outside I'm talking about now. Should have done it on a new page from the start, I think. Um So, now the combined size of these two intervals is still smaller than the outside, then you just forget this separation. That's that's the rule. And this uh intuitively again, it does work with the sizes of the intervals, but it's not a fixed bound. It just says sometimes you should give up a boundary if it doesn't buy you much because it's far away from the outside anyways.

10:23 Okay. Uh Again, let me point out this is an invariant, supposed to be always true. This is a rule that we apply when we call it. It's not always the case that this is enforced. Or that Yeah, the converse.

10:43 And you can show whenever you apply this rule M, question? Uh yeah, the So, this this rule can apply for several intervals. Um wherever you use it, we'll always apply it to all intervals where it applies. Now, the question could be if there is different choices, I think it never makes a difference. Uh of course, it could mean that if you merge two, you don't merge the other two or some something like this could happen. I think it doesn't matter, though. Uh you pick any any choice. What is important is that after you're So, okay, apply rule M always means apply it for all pairs of intervals that you could merge. Do all merges. Do do a a maximal uh set of merges until you can no longer apply it. Which means after you're done with applying the rule, this condition is fulfilled that uh this is always uh bigger than all. And we'll essentially just use this property going forward or you'll you'll see it right here.

11:53 Um after applying rule M, which means no more merges possible. Then we've guaranteed this bound on the number of intervals. Which is one primary feature of this rule. There's going to be a second. But they both follow follow from the same observation. Um Let me even draw the slightly more uh general picture.

12:25 Suppose I have a gap. That's my delta I, the overall thing. And I start looking at some intervals at some random points. I'm interested in in counting intervals here.

12:42 From here to the right. So there may be a number of elements on the left of this. Say X elements here. Uh after these X elements, how many more intervals can I have here when the rule M has been applied? That's what we're trying to look at. Now, there could be an interval here with maybe uh size one. But then there could only be a single one of size one. If I have two of size one and X is at least two or three, then I would have to merge those. So maybe there's one tiny one, but there can't be much more. The next one essentially has to be already of size X.

13:28 And then after that, I maybe have one more of size X. But if I had um That's just the boundary, right? These two together uh so it maybe this already has to be X + 1. Let's Let's be generous and say uh X is still allowed. What was the rule precisely? This is the whether it's less or equal or greater equal.

13:57 Let me copy that so I don't forget. And uh shockingly we've been inconsistent in the two papers I have on this. Uh also shows you maybe it doesn't matter that much.

14:18 So the converse means um if this was no longer applicable, we always have this, right? Um So X + X is not strictly larger than X + 1. So I guess it I can't even have this one. Um we can be more generous with if we start with two times X, that's the large the maximal number we can have. If I had another of size X, then these two certainly would have been merged.

14:49 The smallest size I can have after this is already double X. Anything else, I would have to somehow you merge these two together because left of that is 2X.

15:14 Let Let me do first the the case at the very left boundary. If X is 1, then you know it's you can have three times a one. But these two on the left is still smaller. But then you need to have a two. Now, you can have two twos, but then this uh so these twos together four is still bigger than three. But you can't have another uh two. And if you had a three here, that would be a tie, so that's already a violation, so you need a four.

15:49 You can have one other four, but then you get a again left of that is seven. So, you you couldn't have had a three here. That's already too small. After that, left of that is what? The total from here to here is uh what's that?

16:17 Uh uh in excluding this four is 11. But then um I can't have another four, that would be too small. I need an eight to get above 11. 12. I can have another eight, that's fine. But then you kind of spot the pattern. So, because you always trying to get above the sum on the left it doesn't exactly um grow by a factor of two, but every other time it it does. Or you could say um the first K intervals contain at least two times, and then the growth is only square root two times K. Or you can say square root two times K plus two elements. So, if you continue like this, here K can only be at most two times log delta um minus two, I guess, even. Uh that's the longest you can if you have delta elements in total, you can only have two log delta many intervals. This is if you go from one side. In the general case for a gap, you can go from both sides.

17:47 And so, you have delta half elements for the left side, delta half elements for the right side. Each can go up to two log delta minus one. Uh so, for for log of delta half So, you have this two times, but with delta factor two smaller. And that's still less than four log delta. That was the invariant mhm sharp int. Uh this stronger property we'll need later, that if you start away from the boundary then all these uh intervals here need to essentially do the same doubling, but uh because they you start with X, everything is is shifted by X. So, every of these elements has every of these intervals has to be at least X big. With maybe one exception. Uh the first one may be smaller, but then after that, they all have to have size at least X. And so, you essentially get the same result, but with delta divided by X.

19:37 To get the precise worst case uh for the sizes of the intervals is a bit more tricky. But each case you're adding in X from here and uh you get another X for every interval. So, by and large you're just multiplying those sizes by X. But I think the precise construction is a bit annoying, so let's let's not do that one because you may have the first one a one, so it may not follow precisely this pattern, but effectively it does if you leave out a constant uh the constant first. Um Maybe uh because we don't need the bound to be generous uh the the strict constant factor here. Let's be a bit more generous.

20:17 That's the first important property. If we apply our rule, we guarantee this invariant. So, we have a way to get that done. Uh but of course we don't know how expensive it is to apply the rule.