Video 2-22: Lazy Search Tree Amortized Analysis

0:03 The interesting bits are uh coming now. That is um the amortized analysis of insert and query. That's what we had left. Um let's first look at insert. So, this was what the theorem claimed. Uh that's a bit too colorful. >> [snorts] >> Um and for that we uh remind ourselves of the the steps of insert. Maybe I'm copying these.

0:35 Just the you have to the three As always, we have to analyze the actual cost and the change in potential. And the actual cost, well, for one is the uh balanced search time. That's precisely this term. Uh for two, which is finding the interval within the balanced search tree, it's log delta I, which is at most N. Uh so, it's log uh log of log delta I. So, this N could have been a delta I, but we're generous uh generously upper bounding here. It's within a double log, so it won't do much much difference. That's the time to find this interval, and then inserting this is again, remember, is a linked list, so this is constant time. So, the actual cost for the operation is precisely what is stated. Now, that's fine, but we also need to check if the change in potential uh causes issues. And and here, remember, um we should maybe have a picture for this. Suppose this is the the gap that we do the insertion.

2:03 And it will have some intervals. We don't know exactly what these look like, right? The merge rule may not have been applied for a while. And suppose this is the interval that I am inserting into. So, X goes here. That means this interval is growing by one element.

2:35 Maybe I should say uh plus equal one. Um what does that do to the potential? Well, this uh this can only make the potential for this interval smaller because remember I it may go up by one. Excuse me, the other way around.

2:58 It may go up by one, but it's just a single element. for the potential. Um I might have other intervals that now gain an element in their outside. Uh if this was an interval that had My example doesn't have any intervals. Maybe I'm cheating a bit and make this interval a lot bigger. Now, suppose it had an excess before here. This is the part that that this interval is bigger than the outside. Now, I'm adding an element to the outside, so I can shrink this here by minus one. So, I get a a contribution that even counterbalances the increase of the potential here. Uh but we we don't know if it does and we don't know how many of these we have. So, we can't really use it for anything. So, the overall change in potential all we can say is that is bounded by a constant.

4:11 Um I guess we might also have the case let's put uh bit more defensively big O here. Because might also we might also be in a zero or one-sided gap, in which case the N01 goes up.

4:40 But the increases are only in the interval where I insert or the gap where I insert for N01. All the other intervals either are to the outside of this interval I I insert into, in which case they don't see this new element at all, or they're inwards of it and then it only helps. If anything, it lowers their uh potential.

5:04 So, if I add the uh change in potential to this, I'm remaining with the actual runtime. So, insert is dominated by the actual time we spend on working with the data structure.

5:21 Now, let's look at uh a rank-based query. Again, from the theorem, um this is this is the time we'd like to have as amortized time and remind remember that this X and delta X, this was defined when the new query comes here. The shorter thing is called X, the longer is called C times X for some C at least one, so that it is actually the longer one. Then the amortized time to spend should be X log C plus this log N which from the lower bound we always found we can spend log N time on a query. Okay, let me also get the code for this so that we can refer to the steps.

6:12 I probably want to come back for the other picture. That's that. Mhm. I think it would be useful to also have this this picture here. Um maybe a bit further down.

6:38 Okay. So, again, two steps. We analyze the actual cost and then we analyze the change in potential. Uh the first part is way easier.

6:56 If we go through our steps, uh maybe a bit bigger is is fine. So, um we've already analyzed maybe before we go to the to that part, let's do these two invocations of rule M. These we already separately analyzed. There's a special lemma for them, lemma 2.27. So, for those we we can already cite the total amortized cost and we don't need to look at the change in potential again.

7:47 >> And let's be generous. Um log n is all we need. We could have said log delta. Then uh step one is again searching the biased search tree. That's our log n divided delta i from before.

8:19 But that's also at at most log n. So um here the biased search tree doesn't bias all that much. Uh step three is even cheaper. This is eventually this log log again.

8:35 And again, we can just bound it by log n. Uh nothing really interesting happening there. Um then we have to do the splitting. That's part four. And step five um is again relatively cheap.

8:58 So, let's do step five first. For step five, um we have to generate from the existing gap to new gaps or well, modify one gap and add a new one. Uh the metadata we need to change for that is that now the intervals belong to a different uh diff different gap. Uh that is essentially rebuilding these binary search trees over the gap. But that's again twice log n cost even if I rebuild them from scratch. I have them in sorted order, so that's fine.

9:41 What I also need to do is update the bias search tree because I have to insert a gap there. But again, I can do this in the bias time and I can just generally upper bound generously upper bounded by log n.

10:12 So, all of this is is relatively cheap. Uh the real issue is step four. Because there we have to do the actual work. We have to take our not the gap, but the interval and split it. So, we have something that is proportional to the length of this interval that we actually split. Uh it's also enough because if you look at uh this picture, we do one query, which is a linear time um operation. It could either be a selection query, or it could be something similar. It could be something even cheaper. That depends on the actual query, right? This rank-based query could also be find an element X, in which case it's a linear scan through my interval and I check if I found X or not. Um the point is I spend linear time to produce this new split, and I spend linear time total for the left and right side to partition them a constant number of times further.

11:15 So, within big O, the actual cost is linear in this thing. That's for doing the split. Um and I can do another log n uh I need to potentially update the trees, but um in reality I I don't really need to do this. I I'm I'm doing step five afterwards anyways. So, I would have to insert the new intervals into the tree, but I'm re- throwing away the tree and rebuilding it right after. So, all all that I really have to do in step four is the splits. But, these cost linear time in the current interval size. Um let me write just I for the length of this guy. We're going to write it a few times.

12:07 And we have no bound on this. It could be N for all we know. So, uh that's what it is, um but this is the actual cost in terms of the operation. We'll have to rely on the potential to rescue us here. Um Uh maybe let me make uh clean up a little bit here.

12:47 I think for now that's that's all we need. So, we need to analyze the change in potential, and we really really want that change in potential to be minus I, and maybe plus something that we can uh hide in these terms. We will have somehow we'll somehow have to see this X log C arise.

13:17 But, at this point, um this is maybe also if if you the way we present these proofs once they're done is one thing, but this is a bit different from how you come up with a potential function. Here I always just said, "Ta-da, here's the potential." Um and everything magically works. The way you do this is you start analyzing the actual costs, which are fixed by your choices of the data structure, and then you see how far you get. Uh and there's always a difference between what you want and what the actual cost is. So, we would like to have that the potential is minus I or we say upper bounded plus the cost we have here if we're if we're generous, all of this is fine. It can go up by that much. But it has to somehow eat up this actual cost of linear in the interval.

14:17 So, this is wishful thinking. We don't know if we get there yet. But that's how you get started. Now, in in this case it's not a very didactic example because um it took several iterations to find the right potential. Uh we'll see others where it's a bit clearer that you can really work with uh somewhat directed way from from one to the other. Okay. Mhm.

14:47 We'll work with this picture here a lot. Now, I wonder if I'll just going to move this over. Uh may maybe not. So, um let let me stay here for a bit. There's a couple of cases we have to analyze. Um this wishful thinking part is already done. I promise you the potential we've chosen works for that. Again, remember the potential was this one. All we have to work with is number of elements in not two-sided gaps and then our potential about the the excess size of intervals.

15:38 And so unfortunately we need to have case distinctions for the type of gap that we split and how the query relates to the boundaries. The first big case that we'll look at in detail is that our delta is two-sided.

16:00 The normal case, if you like, and the other two are substantially simpler, but they explain where this N01 comes from and I'll probably just go briefly over this. Um note that this necessarily means that the two new gaps that we generate are also two-sided.

16:25 That makes life a bit easier. Um now there's a further case distinction uh case distinction and we'll look at the harder case whether this interval um so all of all of the following we had we would have two symmetric cases.

16:55 But we always assume that the query is to the left of the middle of the interval that we split. Uh of the That's kind of with loss of generality. It's just a a reflected symmetric case in general.

17:21 That's the picture I've been drawing above before. So, that's the new query, right? And so, uh we also know that the sizes of these two will be X and C times X. Now, this is fixed. This is without loss of generality, I can just flip it around and do the symmetric argument, but there's another case um that I cannot I can only do one arbitrary choice, not uh two dependent ones. This interval that I split may also be on the left side. Um or it may be on the right side. this is a bit awkward if you if you think about the rank being to the left, how can the interval be a right interval? Well, it could be very big. So, um it it could be that the interval is essentially the entire gap. Uh just leaving off a little bit on the left. In general, we have no control over how the intervals look like before a query, unless we apply this rule M, they could be arbitrary.

18:26 And so, it can happen that the interval is all the way is kind of flush right, and you do a query that's closer to the left side, but still the interval you split is further to the right. Okay? Uh but the case we're we're going to be concerned with now is that this is a left interval.

18:50 Um and that's basically the picture here. There is our delta. The query point is to the left of the middle, and also our interval is to the left of the middle. Okay? Uh so, this was the old um I don't know, the old interval. uh I don't want to use colors. Let me Let me leave it. The old interval was this and what's shown in the picture is after the six times after the uh split into six pieces. Okay.

19:29 Now, let's analyze what changes in our potential. We're in the the whole thing is about the change in potential. Uh part one N01 doesn't change. Because we're in the case of uh two-sided gap and the new ones are two-sided, so nothing changes. No element is added or removed from these. So, we're going to ignore this uh for for now.

20:03 And what's left of the potential is all the intervals. And for that, hm we haven't found anything smarter than going through various types of intervals. I'm just going to color those um a bit. There's these kind of intervals, the green ones that are to the left or to the outside of our I I J the one that we split. There's the actual interval that we split. And then there's a few further. Now, my colors are a bit hard to distinguish in the print.

20:43 Okay, I'm going to run out of colors, maybe. There's some intervals that are at the very far right. What these two letters mean uh I can already kind of tell you is before the split this was a left interval. And after the split in the new gap where it resides, it's still a left interval. So, this is before. This is after. And you can have these you could in theory have all four combinations, but you can't actually have the uh the left right. That's because uh if an interval was on the left side and we uh we shrink the gap. So, the for it for it to be on the left side and then turn right, we would somehow have to move the midpoint further left, but that never happens. All we do is that the middle point of the interval before was put somewhere here and now we move it to somewhere here. So, all the intervals only move further to the right within delta I plus one.

21:53 And left of this one, everything was on the left. And it turns out these these might be on the right in the new gap, but that's irrelevant. Uh the important distinction here is just for those that end up in the big gap afterwards. You'll see in a second. And then there's the three cases left. They could be left and stay left. And they could be Let's use this blue. And maybe I can use this blue for these guys. Um or they could be right and stay right. Uh for all of these we'll we'll have to analyze what the change in their potential is.

22:34 And for some it will be easy, for others it will be more annoying. So, uh that's why I'm using all the colors. Um There's also a special one, which is the last one. Last left interval.

22:59 It has to be this guy because afterwards they started uh af- in in in the new gap. Okay. Now, let me try to copy this and make it smaller so that we can keep it on the side.

23:17 If for no other reason than because I will forget which color was what. intervals here that we actually split. So, let's call uh, this phi i because i is the interval we split. Uh, the first thing we do is that we split these. So, we have some some new intervals that are created and some old one that gets destroyed. Uh, uh, for that, let me scroll up slightly to this one. Um, and let's write down the potential of these intervals that we create here. So, the the old interval, we don't really know what the previous, um, uh, potential was. It depends on how big the outside is, but for these new intervals, we know that this is becoming an outside, right? This is a new gap boundary. In particular, this interval will have potential zero.

25:00 That's a new boundary. This guy will have potential zero afterwards because it's protected by exactly as many elements as it is big. Um it would be lovely to say the same for this one, but I'm not sure if we know for sure. I guess I guess this one for sure. Yeah, this one as well because it's protected on either side. Uh I was quickly thinking because it might switch sides. It might be one of those that move uh were left and now move right or something like that. Um All right, it moves left. Uh but either way, it's now protected by as many elements on the outside as it is big. So, these two will have potential zero after the split.

25:48 Uh these guys in here have no protection, so their potential is their size. And for these, we don't know. It looks like they're protected, but this might be the end of the gap. So, maybe it's the leftmost element that we split. So, for these, we can only say the worst is that they're at most their length.

26:16 That's the most pessimistic assumption, and that's the best we can say. So, let's stay with the pessimism, but still what happens um our uh old potential from the interval that was this thing before, uh whatever was. And we gain this orange part. There's a quarter zeros. For the rest, we don't know. Uh so, I I I should say upper bounded.

27:11 But, in the worst case, we have 3/4 I that we gain here. And we have a plus five because we're generating five new intervals. Okay?

27:26 Now, this this thing um all we know is the definition. It's the maximum of the old interval size uh minus the outside of this or zero.

27:47 And so, we do another little case distinction here, depending on how big this I was. If I is at most X, so the uh size of the left new gap then uh even whatever this potential was before, we lose it. So, we can upper bound it by zero.

28:28 And so, what's left is this part, and I is bounded by X. So, I get 3/4 X plus five as an upper bound. And this is big O of X, and you'll see that this is enough.

28:44 Uh in particular, we're allowed to have the potential go up by big O of X log C. C is at least one, so this is always omega of X.

29:03 That's always going to be true. So, this is good enough. If we can bound the change in potential by X, we're happy. So, here we're uh we're getting precisely what we need to um to take away.

29:42 in the case that this interval is small enough is also big O of X. So, um this red term that looked scary in this case is below this bound, and so it actually isn't needed to counterbalance it from the potential.

30:04 So, it's below the X log C. Right? Now, that's i- if you think about it intuitively, the easy case that the interval we have to split is small. The interesting case is when this is really big, because then we have to pay a lot. Uh we again use what we've shown here about this change in potential.

30:41 This time we have to use the full formula, so again this like before. Now we know that this thing is greater than X. But the outside is less than X because look where we what we're doing. We're generating uh a query point here. Anything uh to the left of this interval, the outside, is part of the new gap delta I prime and that in total has at most X elements. So this is certainly less than X.

31:55 So I guess what we're subtracting here is the length of I minus X. Oops. So minus I and plus X at most. That's uh flipping signs, right? But then you see that this is now indeed uh canceling this part.

32:29 And I get 1/4 I release in potential. And this release of potential is what can counterbalance the the actual cost of I. Now, there's a factor of four one one over four in front, which means the overall potential will have to be scaled up by a certain constant at the end of the analysis. That's a typical phenomenon in in amortized analysis that you have to do. You you amortize analyze what your potential does, and if you can show that it's within big O of the cost, you can scale up the potential. That drives up the amortized cost for all operations by that constant factor, but it doesn't change the big O classes, and you can make this minus one quarter, which is really hard to read, eat up the actual cost, whatever they whatever they are. They're linear in I.

33:29 And so, you can make make that dominate. Um the actual splitting cost So, with the right scale, we can make the amortized cost That wasn't too hard, right? So, in a way, uh we had to do this case distinction of how big the interval is, but then it nicely the the release of potential nicely paid for the actual cost we had. Um that wasn't too bad. Now, unfortunately, we have to analyze what happens to the potential to all these other intervals that we mess up. And uh that was also the annoying bit um in in K coming up with the right potential.

34:38 Did that copy the picture? Good. So, let me try to take this with us and we'll just try to go through the remaining cases a bit faster.

34:52 Next, let's look at these green elements, the ones on the far left. So, um these intervals we haven't touched. And their total size is at most X.

35:29 So, whatever we do, their potential is never going to be bigger than big O of X. Even if we mess them up completely, like they're now part of a new gap. We have no idea what uh that does to their outside. Who knows? They might be close to this boundary here now and all pay big O of X. But uh the potential of these things on the left side is always going to be big O of X afterwards. So, even forgetting about what we subtract from before, uh going to be is going to be for free. Or well, it's not for free. Um but it's in within the cost we allow. It only blows up the constant factor, if you like. Uh similarly, these elements on the right that are on the right of the previous um on the of the previous gap and stay on the right in the gap delta I prime, for them, really nothing changes.

36:26 They're the intervals aren't touched. Their outsides aren't touched. So for them the world looks exactly the same as before. Okay, easy cases. Uh Let's next look at these friendly guys. So intervals that were on the left side before and are on the left side afterwards.

36:53 These intervals have a problem because they were left. So this used to be their outside. Now the outside is only this. They're losing X.

37:14 So potentially this is um increasing their potential a lot. Uh but we can bound the number of such potential of such intervals that there can be because remember we're doing this uh within the confines of rule M. We're analyzing the potential after all this. And that's after applying rule M. So we can use the um uh to argue about the number of such intervals. Um I didn't write write down the lemma that we proved there the the number Oh dear. A while ago. Was it before that?

38:32 We had a lemma that bounced the number of intervals uh here. And uh remember this case where I said, "If you start from the left, you can work out that the worst-case sizes of intervals is actually very easy. It's uh precisely the sequence." If you start counting intervals from somewhere in the middle of the gap, you can not easily work out the precise worst-case sizes as it's not as clean a pattern anymore as in this case. But, if you start here, everything on the left has to have uh everything uh here has at least X in their left side. So, all these intervals essentially have to be of size X or apart from a few exceptions maybe, but constant number of exceptions. Whenever you move to the next interval, you gain another X and one more from the interval you skip. So, essentially you can scale everything by a factor X in the sizes, and the number of intervals that you have within a gap of size delta when you skip the first X elements and only count these intervals is this, log of delta divided X.

39:47 That's what we're going to use now. Number 227 26. Why did I read 27? within this new gap whose size is c * x.

40:28 All right? That's the we're talking about elements in gap delta i delta i plus one prime. And so I lost the factor two, I guess uh from the statement of dilemma. It was two times this.

40:53 But the the point is this x here cancels. Let me try make this clearer. So it's uh big O of log c. That's great because that means we have a bunch of intervals in this class LL that are messed up. Their interval outside shrinks by x, so their potential for the interval might go up by x. But we can't have too many of them, only log c time many.

41:29 uh increase is this order log c times order x. And that's again within within the allowed bounds. So only only one case left, these uh light blue intervals that were on the right side and now shift over to the left side.

42:32 >> Just spelling out the obvious things. Um you guys will have to learn something about these intervals. There's one interval, the rightmost of these RLs, which is the rightmost left interval after the fact.

43:02 This one uh we'll ignore because it's a a single middle interval. So, how can this look like? Uh if this is the gap, um we have this rightmost left uh which before was a a a left interval.

44:03 And now uh before was a right interval. So, it the The point of the old gap, that's the delta I before. It was here, but now it shifts over um And then we may have some more intervals that now Mhm. I think I want this to be the new gap.

44:42 Uh but then this needs to be So actually I think I need to shift these guys a bit to make the picture more to scale.

44:53 The point was to argue that they have a lot on their outside. And we again by rule M can bounce using that the number of such intervals.

45:06 Uh here even more extreme, you can show that's only a constant number. So I have very few of these intervals um that switch sides.

45:30 The because they're on the left the outside from before that the change in the outside is at most this X. So the the total contribution of those is rather small. Again um constant number of times times X each which is within our famous X log C.

46:04 Right, they haven't changed, right? These intervals aren't split. So, to count the number of intervals, we look at the outside before or in in the old uh gap.

46:20 There uh they were on the right by uh by definition. So, the outside was was this part. If you leave out the rightmost one, this one, all of them This one's special, but all of these were on the right in the old gap. So, the the old gap continued like this. And they all had an outside that is at least CX half. Because it's half of the right-hand side. It's on It's probably going to be more, but uh at least that.

47:12 So, in the old gap, we can bound their outside. Because the intervals aren't changed, the number doesn't change. Um and applying rule M means we can again take the size of the gap.

47:29 But, I think here this should be delta, so it's it's CX without the divided by two. And we divide by X, the outside, where we start counting, and that's CX half, that's this this right half. And so, again, if you cancel, you get a constant number of such intervals.

47:50 Then this is this one guy left here where we don't know this. Um but what is what is the the in potential for these intervals because they're in the middle uh and they're now left they they may their old right was smaller, but now the left becomes smaller by subtracting X. That means the protection goes down at at most by X. So, for all of these intervals in this range RL uh they all So, for this single interval that we can't uh argue about here, it's just a another one. Right? Um so, that's fine. Okay. Sorry for the confusion. Um To summarize, the outside elements, nothing changes. These blue parts in the middle the uh light blue ones, there aren't actually many because switching sides means you're on the towards the middle and there can't be too many from rule M. Uh the only interesting ones were the the dark blue ones and there we really needed again the doubling or almost doubling of sizes from rule M and that gave us the dominant contribution of X log Z.

49:36 This is all for the case that we looked at, namely case 1 1 where we're in a two-sided gap and the interval that we work with, that we split is also on the left. Um so, the the query is closer to the left and the interval that is split by the query which to the left. Uh there's a bunch of of symmetric cases. Uh I'll I'm just going to list them. All of them are easier than this case. This is the most complicated, so I wanted to do that one.

50:10 Let me just list the cases uh for completeness. If this is a right interval, then uh it's it's actually much easier because because then to the right of this element must be small.

50:42 Uh this case can essentially only happen if this interval is huge. And so everything on the right that took us so long to bound now is essentially big O of X by that. And the rest remains unchanged. Uh remember here the the part to the left of the query point was actually the harmless part. This was uh much easier to bound. And then there's the other cases of having gaps with either no queries so far or having a one-sided query.

51:28 Uh this last one again you need the two uh uh distinctions. Where was the query before? You can have um Then that's actually uh similar to case one.

51:59 An awkward case is this one where the query was on the right. So you're looking at the at a gap that essentially doesn't have a query on the left side, but now you're querying somewhere here. So the intervals here are not going to be in in good shape. They're all going to be fairly big.

52:27 Which means that the the outside of the interval that you're splitting that's your query and that's the the interval. It may have a huge outside because it's uh outside was defined towards the queried side and this one isn't queried. So [snorts] it could be really big. And is that that's essentially the the reason why we needed this extra contribution in the potential. There wasn't any way to bound the change in potential of this interval. This could be huge. It was protected well before, but now you're cutting a query here and all this protection is gone. Uh but in this case note that all these elements here are now two-sided are now within a two-sided gap. So all of them lose this uh N01.

53:22 So here you need this part. And then this can be uh this can pay for that part. Uh this case two is actually easy because then we always have a single interval.

53:50 Well, this is like the first case, the red one where you only have to worry about paying that single interval split. So, in in a way um this last case, 3 2, I didn't explain all the details. For all the rest, you've seen the full details. So, this is This is all there is to do. Um It's a lengthy case distinction where you have to argue about what these intervals can look like and how many there are. But again, the essence was this dark blue part. That's the dominant contribution.

54:37 Okay. End of lazy search trees. Uh you've seen how they can effectively treat at least insertions and queries in a sense optimal, namely meeting this multiple selection lower bound. If you serve any sequence of insertions and queries, the total cost you pay um is within this B plus N plus an N log log N this overhead. Uh and per operation, it's never worse than the log N of a standard binary search tree in an amortized sense. Uh if you do it over all the queries in over all insertions and queries, uh single queries can be more expensive, but only if you've had a lot of insertions that were cheap. So, in a way, you've profited earlier. Uh if you look at an entire sequence of insertions and queries combined, you never pay more than a binary search tree and sometimes much less because the insertions can be much cheaper. Uh a clever little trick is we've talked about splay trees a bit.

55:44 You can use splay trees as a biased search tree. And you can use splay trees also as a balanced search tree. So, you can build all of lazy search trees using two layers of splay trees. And uh because splay trees have these wonderful guarantees that we talked about earlier, uh lazy search trees can essentially inherit the same by just using splay trees under the hood. And so, you can get stronger results than what we've shown uh if the queries are for repeated elements. If you query the same rank again, the same element again, there is no actual split needed. You just find the element as one pivot splitting uh some intervals. And in that case, because the uh gap level splay tree restructures itself cleverly as splay trees do, uh you get these similar access guarantees as for splay trees.

56:45 Um another cool thing that we put a lot in as the motivation for splay for for lazy search trees, but I haven't talked about it all, is what happens if you use lazy search trees as a priority queue, which means you're restricting the queries to only ask for say the minimum. Finally, you can you can without any effort ask for minimum and maximum, and it's going to be roughly the same. Um but in particular, if you only ask for for the minimum, say, you get the standard operations for a priority queue. Uh we can change the keys in the right way. This turns into a decrease key operation. Uh and there, you immediately get, without any extra work, that um you beat standard binary search trees a lot because here again insertions and decrease key take log log time not log n. That's not quite as good as we'll see in the next chapter as you can do if you only support these.

57:45 But the important point is that the data structure doesn't know up front. You just use it as a priority queue then it behaves like one. If you start adding more queries in the middle it'll serve those but then future insertions are more expensive. But it happens automatically.

58:07 So it's kind of interpolating between these two extreme points. You can say these are the end points of a spectrum and any any point in between also makes sense. And you can use lazy search trees to serve those. One caveat something I think I successfully swept under the rug so far is this notion of optimality is one way to define it. But you can also define it differently because we're essentially comparing it to a multiple selection lower bound. This means I'm implicitly inserting everything first and then do a bunch of queries. Now it's clear if I would do all queries first on the empty tree where they all make little sense and then insert everything afterwards I should be able to do better.

59:03 Um I don't know if this is clear enough at this point. Lazy search trees remember all past queries forever. If you've ever queried at a certain rank any future insertions are split along that rank as well because the gaps are never combined again.

59:20 You could think about such a a data structure that tries to combine gaps again but it's not even clear what the goal would be. We don't have a clear lower bound to work against. It's only obvious that insertions after any queries should be for free because you're never looking at these elements that you insert there at all. So, why split them around the past queries?

59:46 The answer for lazy search trees is, well, to make my amortization work. This seems inevitable. Uh but in principle, there should be something better. It's just not so obvious what the the lower bound is one has to work against to make anything work. But I wanted to leave uh not not leave that unmentioned.

1:00:08 Uh in a way, you can be even more optimal. Well, that's for another time.