This preview effectively demystifies the segment tree by focusing on the core logic of logarithmic optimization rather than just rote memorization. It is a pragmatic, high-density guide that provides a clear roadmap for mastering one of competitive programming's most essential data structures.
安装我们的扩展，即时搜索任意视频内容
Introduction to Segment Trees | TLE Level 4 Course Preview | Taught by Priyansh本站添加:
Okay. Um, so hi guys, welcome to this lecture on segmentries. This is the first class on segmentries. So we'll start from the absolute scratch. We'll understand where exactly is a segmentry needed. Uh, you know, what are all the operations that you can do with a segment and how efficiently can you do those operations, right? So yeah, let's let's begin. And for that, let's first of all solve this first problem. You are given an array of n elements and q queries. In each query, you will be given two indices L and R. You need to output the sum of values from the index L to R in the array. Okay, the array is not going to change. All the queries are going to be of the form L comma R. This L and R can range from 1 to N. And you just need to output the sum of values in that range or in that subarray. Right?
So you can take this as an example.
The array is 35 28. The first query is 2 to 3. So this is index 1, index 2, index 3 and index 4. Right? So we are referring to the sum of these two values 2, 3 like 2 to 3. Similarly, uh for this query, we are referring to the sum of elements from 1 to 4.
Okay, how can you do this?
Yes, we can use a prefix sum.
Okay, this is a pretty easy problem. We can use a prefix sum for it. Does everyone know what is a prefix sum?
Is there anybody who does not know what is a prefix sum?
No. Okay, cool. So, um I'll just give you the idea very quickly. Uh how can you use a prefix sum? Although like this can look this can be like a revision for all of you. So, when you have an array, um let's suppose this is the array, right? Um let's draw some partitions.
So when we talk about prefix sum essentially what we do is that we create another array we create another array let's call it pf.
Okay.
So how this prefix sum array works is that PF of I the value present at the if index in PF of I is equal to sum of values from U let's call it U J is equal to Z up till I in the array.
Okay. So when we talk about let's suppose this particular value this particular value is going to be the sum of all these values.
Okay. Does that make sense? This is how we define a prefix sum array. Now when we want to find out the sum of uh like let's suppose we want to find out a of l plus a of r sorry a of l + a of l + 1 plus a of l + 2 so on up till a of r.
How we can solve this is let's say we want to like find out the sum of values from here to here. Okay let's suppose this is r and this is l. Now when you look at the prefix sum array, if you look at the value present at PF of R.
What is PF of R?
PF of R is equal to sum of values in the array. I is equal to zero up till R right inside this array A. Now we don't want the entire value from 0 to R. We want the value from L to R. Right? So there is something that we need to subtract out. What is that something that we need to subtract out? Uh if we have the sum from here to here, we essentially want to subtract out the sum from here to here because this is something that we don't need, right? How can we subtract it out? We can simply say uh like we can subtract PF of L minus one from it and that will just give us the values from N tor. So um PF of L minus one P of F of of L minus one will be I is equal to Z up till L -1 A of I now when you do PF of R minus PF of L minus 1 what do you get? You get this value you start from I is equal to L.
You go all the way till R and you say a of I right this is exactly what we wanted.
We wanted the sum from L to R and this is how we can get it from this array or from this equation.
Right? So with a prefix sum what you essentially do is that you spend order of n time order of n um time and space for premputation.
Right? You spend this time for premputation and uh every time you get a query now you can answer that in constant time. Is it clear to everyone how a prefix sum works?
Yes.
Okay. Cool. Let's uh go to the second problem. So the overall time complexity for this with a prefix sum will be how much?
time and space with prefix sum.
This is going to be order of n plus um q like you can say uh time is order of n uh sorry time is order of n plus q this is time and order of n is the space okay let's move to the second problem so again you're given an array a of n elements uh which is initially filled with zeros okay the entire array is filled with zeros and now you're given q queries in each query you will be given two indices L and R and you will also be given an integer X. You need to add X to all the indices of the array from L to R. Okay. And then after you have processed all the queries, you have to print the final array.
Right? So you can take this as an example. If the array initially is 0 0 0, then the first query is 2a 3a 6.
Which means that you need to go from the index 2 to index 3 and you need to add a value of six to all these values. So you basically added a six here and here. The next query is 1 4a 7 which means that you need to go from index one to index 4 and you need to add this value seven to all the indices. So you added a seven here, you added a seven here, you added a seven here and you added a seven here.
This is the final array that you need to print.
Okay. Now obviously the catch here is that n is going up to 10 ^ 5 and q is also going up to 10 ^ 5 and we know that if we were to brute force this whole solution that if for every single query if we go from l to r and and we keep adding this value x to all these indices for every query on average it will take order of n time right so if we were to do a brute force if you were to do a brute force the brute force would take order of how much time order of Q into N right so brute force we are not allowed to do we have to come up with some efficient solution for this so in the previous problem the array was constant and for every query you need to you had to print the sum of values from L tor in this problem the array is not constant it is going to change with every single query but you don't need to print the answer after every query you need to print it at the end of all the processing right how can we do Yes, we can solve it using a difference array, right? This can be solved using a difference array. How many people don't know what is a difference array?
Line sweep. No, I don't think line sweep is required here. Line sweep is a pretty complex algorithm. Um, it's not required here.
Is there anybody who does not know what is the difference array? Because if you don't know then I'll go slowly in that.
If you already know then I'll just quickly rush through it as I did it for prefix sums.
Right? So maybe write a plus one if you don't know what is a difference array and I'll maybe go deep into it.
Is line sweep and difference array not the same concept? No, they're not they're not same. Line sweep is a different concept altogether.
It's not the same as difference.
Okay. So, everyone knows about difference arrays, right? Write a plus one if you know about difference arrays.
Okay.
Again, I I'll ask this again. Is there anybody who does not know what is the difference? I write a minus one. I'll go deep into it. Then if you don't write a minus one, I'll just quickly rush through it. So you will have to tell me if you already know about it or not.
Okay, I see one minus one.
Okay, cool. Let's try to understand what is a difference array. It's not a very complex uh topic. You'll understand it very quickly.
See, let's suppose this is your entire array.
Okay. Now let's break it down into some partitions or indices.
Initially this entire array is filled with zeros. Okay. So this is what you have.
Okay. Now if I tell you that you want to add X to all the indices from U like let's number these indices uh 1 2 3 4 5 6 7 8 9 10 and 11. Okay let's suppose this is your query u 3 comma 6 uh 8. What does this mean? It means that you need to go to this um you need to go to this index, this index, this index and this index and you need to add a plus 8 to all of them. Right? This is the query. Now how can you process it efficiently? See uh what are the what are the points that really matter to you? The points that really matter to you are three and six. Right? If you can do some sort of uh clever uh you know optimization by adding something on three or adding something on six or subtracting something on three or six and later on later on doing something else you might you might be able to solve it right our our goal here is to process this single query very quickly we don't want to go through every single index from 3 to six and uh you know process it so one of the ideas that comes up is that if I add a + 8 to three if I add a plus 8 to this index.
One second.
Now, think about it. If I add a plus 8 to index 3 and if I then take the prefix sum of this array, what will the array look like?
If I add a + 8 to index 3 and then I take a prefix sum of the entire array, what will my array look like? This is how my array will look like. Oh, one second.
Or rather, I'll just copy this entire thing.
Okay, if you add a plus 8 to index 3 and you take a prefix sum of this whole array, it will look something like this.
You will have an eight here, eight here, eight here, eight here, eight here.
Are you able to understand this? I added a plus 8 to index three and then I took a prefix sum of the entire array. This is how my array will change. Now, do I really want this eight to affect all the indices or do I only want it to affect from 3 to six? I only want it to affect from 3 to six. So, what do I need to do?
I need to somehow cancel these values that are present here. How can you do a cancellation here? Exactly. If you do a minus 8 on 7, if you do a minus 8 on 7 and then you take the prefix sum, how will the array look like?
If you do a minus8 on index 7 and then you take the prefix sum, how will the error look like?
Your this will become 0 0, right?
See, of course, taking the prefix sum is a is a heavy operation. It takes a lot of time. it takes order of end time. But what I'm saying is that you know I don't need to take a prefix sum after processing every single query because I need the answer or I need the resultant array at the end of all the queries. So what I can do is that I can process every single query like this that for index L I will add an X and for index R + 1 I will add a minus X and then once all the queries are processed I will take a prefix sum of the entire array.
What will that do for that? every single query that we have uh like put in like if you have add added x to l it will continue traveling until index r and at r plus one it'll automatically get canceled out because we have added minus x there does it make sense to everyone this is known as a difference array so we can take a very quick example um yeah let's suppose a is equal to this Initially all of it is zero.
Right? Now you want to process let's suppose three queries. Uh first query is of the form um two like these are indices 1 2 3 4 5 6 7 8 9 10. Okay. This is the first query.
2, 7, 3. Okay, which means that you need to go to index two up till index 7 and you need to add a value of three. The second query is um you need to go to index um from index let's suppose three to six and you need to add a value of five.
The third query is that you need to go from index um let's suppose 8 to index um 9 or let's suppose index 8 to index 10 and you need to add a value of two. Okay, let's try to process all these queries. So for the first query, what will we do?
For the first query, what do we want to do? We want to add a + three to index 2 and a minus3 to index 8, right?
Just process all of them here.
Okay. So for the first query, what will we do? We'll add a + three to index 2.
So we'll add a + three here.
and you want to add a minus3 to index 8.
Okay, let's come to the second query. We want to add a uh so this will this will obviously change. We have a three and a minus three already here. Now, how do we process the second query? Uh we want to add a five to index three. We'll add a five to index 3 and we'll add a minus 5 to index 7.
Right? So we're adding X to index L and we're adding minus X to index R + 1. So that when we take a prefix sum, the value that we have added at index L, it keeps on traveling towards the right side and it gets canceled out on index R + 1. Okay, let's come to the third query. So this will remain like this 3 5 - 5 and minus 3. Now it says that add two at index 8. So at index 8 we already have a minus3. So we'll add a like we'll add a two to it. So it will become minus one. Okay. And then at um like we want to add now a minus2 at index 10 + 1 which is 11. So do we really care about index 11? No. Because it is outside the array. Nothing is going to change if we if we add another index 11 at the end of the array and add minus2 to it. But we are just concerned about the resultant array. We're not concerned about what happens outside the array. So we'll not do anything here.
Does it make sense? We only add a minus x to index r + 1 when r + 1 is valid.
Right? Now once we have processed all the queries, take a prefix sum of the entire array. How will the prefix sum look like?
This is resultant.
Okay. So this uh this is the array before we have taken the prefix sum.
Okay. Now we'll take the prefix sum. So prefix sum will look like this. 0 3 8 8 8 8. This will become now a three. This will become a two. And this will continue like this.
Okay. Have we reached the final state?
This is is this what we wanted?
Sorry. This is this is not uh zero. It should be two and two. My bad.
Is this what we wanted or is did we want something else? So this this took order of one time. This took order of one time. This took order of one time. And then finally when we wanted the resultant array, it took order of one time.
Have you understood for people who did not know about difference arrays? It is an optimization technique to perform range updates very quickly. Okay. And range updates specifically where uh you know you can add something to L and you can somehow cancel it out at R + one.
Okay. Um now if you if you understood this whole idea uh since you have moved a little fast I'll just cover a quick problem. Uh let's suppose u like or before that let me just first of all give you the idea. So what do we do in difference arrays?
So we say that um add x at um let's suppose index l and we say that uh subtract x at index r + We want to do this for every query.
Okay. Once you have done this for resultant array, take the prefix sum.
Okay. So this is how this is what difference arrays look like. Um I thought this is line sweep only. No, this is not line sweep. Line sweep is a different idea. This is not line sweep.
Okay.
Yeah, this is difference for you. Uh you might want to try this uh problem out as well. Like let's suppose I give you this um problem that um given an array uh a of n elements filled with zeros initially and Q queries.
Okay, every query is of the form L comma R comma X and um basically what you want to do is uh take the zor like or rather say something like this.
This this query means make uh every value in array.
every value in array let's call it a of i from l to r as a of i is equal to a of i zor zor x okay have you understood the problem you want to do this for every single query you are given two indices l and r and you're given an integer x what you want to do is you want to um go from every index L to index R and whatever value is present in the array currently A of I just make it as A of I is equal to A of IR X right you're given Q queries the size of the array is N uh we can say that Q is going up to 10 ^ 5 uh N is going up to 10 ^ 5 and now you want to find out the resultant array.
Can you solve this?
Same idea. You have to do something at index L and you have to somehow make sure that at index r + 1 it gets canceled out when you eventually find out the resultant array.
Okay. So if let's suppose we take this array itself.
Okay. If this is your array, let's suppose I give you a query like um 2 comma 5 and you want to thicker users or with four. Then I give you another query where I give you indices uh three comma uh 8 and you want to take a zor with two. Okay, what can you do now?
See if you take like when you're given index l and r and you're given an integer x if you take a of if you make a of l is equal to a of l zor x right and then you eventually take a prefix zor what will happen like I am saying that if you uh if you take a zor of index like whatever value is present at index two with a four so this will become a four yes this will become a four. Now if you take the prefix zor, how will the array look like? Your array will look like 0 4 4 4 4.
This is how your array will look like.
Now if you want to cancel it out at index 6, you don't want the zor of like you don't want the value four to get propagated further. What will you do?
You will take the zor again because x zor x is equal to zero. If you take the zor of a number with itself, it becomes zero. So it gets canceled out. Does it make sense?
How can we process this? We can say that um like we'll just paste it here, right? We'll uh replace this with a four like we we'll say a of l is equal to a of lzar 4. This will become a four and at index again we'll take a zor of four.
Right? Now let's move to the second query.
So this is already four.
This is four. Now at index three, we'll take a zor of two. And at index 9, we'll take a zor of two again. Right? Now finally take the resultant prefix zor.
How will the prefix z look like?
Okay. So this will be uh 0 4 6 6 6 2 2 0 and 0.
Yes. Is this what you wanted?
Yes. This is what you wanted.
So are you able to understand how did we how were we able to do the same thing with Zor because we had a mechanism to do something at index L and then cancel it out at index r + 1. Now tell me one thing can you do the same thing if I ask you to do something like this that go from every index L to index R and multiply the value with X. Can you do the same thing?
Like now the query will change. Now the query is go from every index L to uh from index L to index R and then multiply the current value with X.
How can you solve this? You can again do the same thing. You multiply A of L with X and you divide A of R + 1.
Can X be 0? No, X will not be zero. Like just for simplicity, X will not be zero.
X will be a positive number. Let's suppose and the initial array is let's suppose ones. Initial array is not zero.
initial arrays once. Can you do can you do the same thing again? Yes. You can multiply a of l with x and you can divide a of r + 1 with x. And then finally when you want to find out the resultant array, you can take the prefix multiply. You can take the prefix multiplication of the array.
Does it make sense to everyone how this resultant sorry this difference array concept can be extended to other problems.
So Kavi is saying one query prefix zor would work here because entire array is only zeros right and not if we would have no so if you have an array with does not which does not contain zeros initially what can you do you can create a temporary array which contains zeros initially right and you can do all the queries on that temporary array once you have found out the temporary resultant array then take the zor of the temporary resultant array and your current array and you will again get the same value.
So the cool part about difference array is that even if the values initially are not zeros or if the values are not initially ones, what can you do? You can basically separate out the current array from like you can make a temporary array which initially contains zeros or which initially contains ones, right? You can perform all the queries on the resultant array. Sorry, the temporary array and then when you want to find out the resultant array, you can combine the temporary array and your original array.
Right? Does that make sense to everyone?
Okay, so the question was that if the array initially did not contain zeros, then can you do the same zor thing here?
No, you can't because the prefix zor would not really work that way. So you can create temporary array which initially contains zeros. Perform all the queries on the temporary array and then merge the two original and temporary array by taking a zor of every index with itself.
Okay, so this is difference array concept for you. Uh so this problem can be solved in how much time? Uh it can be again solved in order of n plus q.
This is time and order of n space.
Okay. So we have looked at two problems.
One of the problem was when we want when the array was static and then we wanted to find out some range uh you know we wanted to do some sort of range query but the array was not changing right. uh which we were able to do with something like a prefix sum. In the second problem, we said that the now that now the array is going to change but we want to find out the uh you know we want to find out the resultant array at the end of all the operations. For that we used a difference array to do all the operations efficiently and then finally took a resultant prefix sum which gave us the resultant array. Right? Now we want to do something like both of these operations really quickly. Right? Right.
uh we will have an array where we'll have updates u where we'll we'll be given that at this index update the value to something and then at the same time we want to find out uh some range query efficiently right so this is the problem now given an array of n elements and q queries each query is one of the two types the first query is of this type that um change the value at index this given index to x whatever value is present in the area at this index change A tox and the second type of query is find the sum of all values from L to R.
Okay. Do we have an example? Yeah, we have an example as well. Uh but before that um what I want to tell you is that these queries can be interled. It does not mean that all the first type of queries will come like this that this is the first type of query and then we have the second type of query. This is very easy to solve because you can basically do all the updates from here to here then build a prefix from here and then process all these queries again. This is very easy. We don't have a problem like this. We have a problem where the queries can come something like this. 2 1 one something like this.
Okay. So the queries are going to be interled which means that you don't know um if all the queries of type one will be given before all the queries of type two. So it can happen that all the like you have a query of type one then you have a query of type two then you have a query of type one and then you have a query of type two. It can happen like that as well. So here's an example.
Uh this is the initial array which is given to you. Uh 4 512.
Um the first query is of type two. Type two means that you want to find out the sum of values from index 3 to index 4.
So um this is um index three. This is index four. So the sum of values is 1 + 2 which comes out to be three. The second uh query is of type one. Type one means that you need to go to index three and you need to change the value to seven. So what will our array look like? Our array will look something like this 4572. Initially it was 4 512.
The third query is of type two again which need which means that you need to find out the sum of values from uh index 2 to index 4. So index 2 is this uh three is this uh four is this. So you have 5 + 7 + 2 which comes out to be 14.
Have you understood the problem statement guys?
Okay. So yeah n and q both are going up to 10 the^ 5 which means that you cannot do something like n into q. So obviously the brute force idea would have been something like this that every time you have a query of type one uh change your entire array and and build a prefix sum again on it so that the second type of query can be processed very quickly. But uh if let's suppose all the queries are of type one. Uh let's suppose half of the queries are of type one then you would have a time complexity of n into q which is not what we are okay with.
Okay. So I I won't give you a lot of time to think about it because that is what exactly what like that is exactly what you're going to learn in this class. And this is something that can be done using a segment tree. Right? Uh this problem can be solved using a segment tree. and similar problems where you have some updates being done on the array and then you have range queries being done on the array in in an interled manner then you need something known as a segmentry right a segmentry can do both of these operations in login time it can do an update in login time and it can do a range query in login time right so if you're able to do both of these in login time then our overall time complexity would be how much q into login if you're able to do every single query in login time right so let's try to understand u what exactly is a segmentry right um and as the name suggests when we talk about segmentry uh what we trying to do is that we're trying to divide the complete array into multiple segments okay so this is how your segmentry actually looks like so essentially what we do is we look at um the entire array from let's suppose so this is the given array that you 0 to uh 0 1 2 3 4 5 6 7 uh yeah this is the array that is given to you. Okay, right now we are looking at them as individual values. Okay, so this is index uh 0. The value is zero. Index one has a value of 27. Index two has a value of 44. Index 3 has a value of 93. Index four has a value of 14. Index 5 has a value of 40.
Index 6 has a value of 10. And index 7 has a value of 21. So this is the initial array that is given to you.
Right? Now what exactly is a segment? A segment tree is like uh you know you look at the entire array as your first node. So this first node consists of the entire array. Our entire array is from index where to where 0 to 7. Okay. Now this first node is going to have two children. The left child is going to contain the first half of the array. This uh right child is going to contain the second half of the array.
Okay. So this is node one. Node one is the first node in the tree. This is the root of the tree. basically right now this root has a left child and the right child. So for the for the root of the tree your values were from 0 to 7 right this was your range this 0 to 7 right when we want to find out the left half we basically say that we are going to pick up half of the elements so what are going to be half of the elements 0 to three right so this is the first half of the array and similarly the second half of the array will be from 4 to 7 now when you look at the first half of the array you can again imagine it as a as a as a segment right now. This big segment can again be divided into further two segments. What will be these further two segments? This 0 to 3 can be divided into two parts. The first part will be 0 to 1. The second part will be 2 to 3.
Now again this 0 to 1 can be divided further into two parts which will be 0 to 0 and 1 to 1.
Now are you able to understand this one thing that as you continue dividing the array into halves every single time eventually you will reach a place where you are only left with one single item or one single element.
Yes or no?
Yes. As you continue dividing the whole array into uh halves eventually you will reach a state where you only have one element left in the whole subarray that you're talking about. right now.
So this is what you do basically. Um you I can maybe draw another um segment if you want.
Yeah.
One second.
Okay. So this is how our segment looks like. Um and um every node in the segment. So like this is a node. You you have already studied about trees. So you know what are nodes and what are edges.
Um so this is a node. This is a node.
This is a node. Okay. All of these are nodes.
This is a node. Uh this is also a node.
This um leaf is also a node. Like this is a leaf node. If you have like you already know about trees. So this is a leaf node.
Leaf node corresponds to an actual u element in the array.
Okay. And every node is uniquely determined by its start and end or by its left and right by its left and right end.
Right? So um another thing is that you know um nodes which are higher up in the tree like higher up in the sense that which are closer to the root they're going to contain more elements more elements from the array. So let's write that as well. Like these are all obvious statements by the way, but I'll still write them.
Nodes um closer to the root have um are wider. Let's suppose all right which means that they have uh more elements from the array.
Okay. Are you first of all able to understand the structure of the segmentry?
What exactly are we really building? We have the entire array at every level. we continuously divide the array the the current array that we have into two parts. So initially you have index 0 to 7. How will you divide it into two parts?
So um this is L, this is R or let's call it um let's call it S and E. How will you find out what is going to be the range for the left half and what is going to be the range for the right half?
The range for the left half is going to be S. And let's define our concept of mid. So m is equal to s + e by 2.
So this is going to be s and m. And this is going to be m + 1 and e.
Does this make sense? Let me write it maybe in a better way.
Okay. Let me take it here.
So this is going to be M plus1 and E.
Okay, you can again u like use the same concept here. Um if you look at this like uh here you have 0 and 7. So what is going to be made? 0 + 7 by 2 it is going to be three. So you have s is 0 and m as 3. And here you have m + 1 as 4 and e as 7. You can apply the concept the same concept here. So if you have s is equal to 0 and e is equal to 3 m is equal to what?
M is going to be 1. So you have 0 and one here. 0 and one here. And you have m + 1 and e here 2 and three here. Are you able to understand how we are basically going to the left and the right half.
If your current range is S to E, you can go to the left half by saying S and M.
And you can go to the right half by saying M + 1 and E. Clear to everyone?
So you have an initial array and on top of that you have built a tree, right?
We'll see how we can like how this tree can help us do both of those operations in login time. But first of all, you need to understand the structure of the tree. The structure of the tree goes like this that the top node has the entire array and as you keep going down the tree you divide your current node into two halves right and you basically look at the left and the right child okay first of all let's talk about um what is going to be the um let's talk about one second yeah let's talk about what is going to be the space complexity of uh building a segmentry How much space is a segment going to hold?
Any guesses on this?
See, most of the people who are saying 4n or um 2n or order of n um already know about segmentaries because they're they're talking about an optimized version of the segment. But right now, what are we really storing in a segment?
If we have a segment like this, let's um make it a bit more clear.
If let's suppose you have this as your segment tree.
Okay. How much space is the segment going to store?
The first level has how many nodes?
First level.
Sorry, not nodes. But how many how much space is the first level storing? It contains the entire array, right? The first node contains the entire array. So how much space is is it using first node? How much space it is using?
It is using order of n space. Right?
This is n. These are n elements which you're storing in the first node.
Correct? So this is n. Okay. What about the second level? The second level has how many nodes? Second level has two nodes. And each of these nodes are storing how much uh how many elements?
nx2 elements. This is storing n by2. And this is storing n by2. Okay. What about the third level? Third level has four nodes. And each of these nodes are storing how much? It is storing n by4.
Right?
Similarly, if you go to the fourth level, the fourth level has eight eight nodes. And each of these nodes are storing how much? N by 8, nx, n by 8, n by 8 and so on. Right? So can I say the amount of space that I'm using?
The amount of space that I'm using is on the first level you have one node and you have n elements. On the second level you have two nodes and you have nx2 uh elements. On the third level you have how much?
You have four nodes and nx4 elements in each of them. And you keep going like this.
Now tell me one thing. If you have a value of n, how many levels will it require to break it down into one element? If you have nodes in in the first level, how many levels will it require to get down to a place where you have just one element in your subarray?
So see you want this like n by like if you look at it like this nx4 and so on. Can I write it as something like this?
summation of K is equal or like level is equal to 1 L is equal to 1 um up till some value where you have L sorry not L but 2 to the power let's start with zero okay one only 2 ^ L -1 * n / 2 ^ L - 1 this is what we Right now what is going to be the upper bound here? Like you start with one till what level will you continue doing something like this? You will continue doing something like this until this value.
This value what does this value tell us?
This value tells us the number of elements from the array in a node at level L.
Yes. When does when does our segmentry stop dividing further?
When the number of elements in our current subarray in the current node equals to what? it becomes one when you reach the leaf node. So what do we want?
We want um so for leaf node you have n by 2 ^ l - 1 becomes 1 right which means that um n is equal to 2 ^ l - 1 which means that l minus 1 is equal to log n log base 2n which means that l is going to go up till log 2n n + 1 right? So what can I say about this?
I can say that u the overall space complexity is going to be l from 1 up till um log 2n + 1 and it is 2 l -1 * n / 2 - 1 right this gets canceled out so this eventually becomes what it becomes n * what log 2 n + Which is how much? Which is approximately n login.
Yes.
So this is n login space. When when do we have this much space?
When do we have this much space?
when for every node we are storing the entire subarray into it right so even when we are storing the entire subarray into a in a node of a segment it's not taking a lot of space right is n login a very huge space I don't think so n login does not look like a very huge space to me right so even when we are storing the entire subarray for which for that node into that node overall the space complexity is going to be how much n login, right? But the whole point is that do you really need to store these values? Do you need to store the entire uh subarray into a node? And the answer is no. See, when we're talking about this problem, what do we want?
We want to find out the sum of all the values from L to R.
Do we really need those exact values?
like do we need those exact values from L2R or do we just need the sum? We just need the sum, right? So is there a need to store the entire subarray for every node? The answer is no. What you can do is that you can just store the sum of all the values in that subarray into that node. Right? So I'll just tell you how we can do that.
So this is when you have um when we store the entire subar in every node.
Okay. Now, so this is one of the uh segmentaries that we have, right? I hope this is not very small and you're able to read it. And this is the second type of segment that we have.
One second.
Okay, let me maybe Recolor this.
See if if I give you that the initial array is something like this.
If I give you that initial address is 2 1 3 2 6 2 1 1 right. How will my segment look like? If I store all the values in every uh in every node, it will look something like this. This will be a two.
This will be a one.
Okay, this is how your segment tree will look like if you store the if you store the exact values in every single node.
Right? Now, if you don't want to store the exact values in every single node, what you can do is you can just store the sum of values in that u in that node. Right? So let me first of all change this to a zero.
Okay. Now so you can have a two here, a one here, a three here and a two here.
Then a six 2 1 and a one. Right? Now if you look at the nodes in the upper levels, let me write it properly. This is going to be three. This is going to be 2 6 2 1 and 1. Now in the upper levels right in the nodes um which are which are uh above the leaf nodes what you can do is instead of storing the exact values you can just store the sum. So here you can store the sum of the left child and the right child. This will be a value of three right here you can store a value of five. Here you can store a value of eight and here you can store a value of two. Then here you can store a value of eight again this will be 10 and this will be 18.
Right?
Now tell me one thing u when you talk about updating a particular um value in the array right so let's suppose you have built a segmentry on the array now you want to update a particular value in the array how will you actually update it if you have these two types two types of structures how will you update it in the first structure let's suppose I give you this thing that u update index um update the value at index two to a value of five which means that you need updated here, updated here, updated here, and updated here. Right? If I just update these four values, will my entire segment become updated?
Yes or no?
If I just update these four values, will my entire segment tree be updated? The segment tree is basically like a tree built on the array. Now, whenever we get an update on the array, we want to update the segment tree as well, right?
because this segment we are eventually going to use for doing range queries.
So when I get this um update that update the value at index two to a five what this means that I need to update here five.
I need to update here five.
Yes.
Can I do the same thing on this array on this segment that we have here where we don't store the exact values but just we store the sums?
Yes, because we can start from here. We can say that okay we want to reach index two. Okay, I think uh this is a bit um like I' I've used zerobased indexing while drawing and I've used one based indexing while explaining. So this is going to be index 1 to five. Update the value at index one to a five.
Okay, this is zerobased index. So we want to update this particular um index.
How can we do it? We can start from the top of the segment. We can uh like right now I'm not telling you how will we reach the exact node but just assume that there is a way. I will teach you how how that is done. So you'll come here. You'll come here. Now when you reach the leaf node, you'll update this value to a five. And while you're going back up, you will just recalculate all the values.
How much time will it take to recalculate this value? By the way, once I know the value of the left child and the right child, how much time will it take to re recalculate this value? It will take constant time, right? Because I can just say left child value plus plus right child value. This will become a seven.
Okay.
Now this will become 12 and this will become a 22.
Right? Are you able to understand how we have done this? There are two ways in which you can build a segment tree. One is that you store every single node that is present in that sub array within the node. The other way is that you just store the sum because you're just interested in the sum, right?
Okay. So now let's talk about like we we'll only look at this type of a segmentry because this is a more optimal way of storing values. We don't really need to store all the values. Okay. So what is going to be the space complexity for this type of a segmentry?
How will you find out the space complexity here in the first node? How much sorry in the first level? How many nodes do you have?
In the first level, how many nodes do you have?
You have just one node, right? How much memory is that one node storing? How much memory is that one node using?
Constant memory. It is not it is not storing all the n values. Now, it is just storing a single integer. So, for the first level, you have one node which stores constant time uh memory. Right?
Now, for the second level, how many nodes do you have?
For the second level, how many nodes do you have? You have two nodes.
Right. And how much memory are is each one of them using? Constant time, constant space, sorry.
Right. On the third level, how much spa memory do you have?
Again, four nodes and constant memory.
So, this is going to be one, right? This is going to go all the way up till n like you will reach a level where you have nodes, right? And this will again store every node will store a memory of n sorry, memory of one, right? So what will be the total memory?
Can I say n + nx 2 + nx 4 + n by 8 so on up till 1.
Right now we're not looking at the case where n is not a power of two. Let me just write it here. Assume that n is a power of two right now.
Okay. Which means that um your your tree will look exactly like uh at like at the last level you have exactly n values you have exactly nodes. If n is not a power of two of course the tree will not look completely balanced right there might be a certain uh node there might be a certain level which does not have exactly that many nodes which are supposed to be in a balanced tree.
Right? Right? Now if we assume that n is a power of 2, can I say the space complexity will look something like this? n + nx2 + nx 4 + n by 8 so on up to 1.
Right? How much is this value? Does anybody know the result of this value?
This is 2 n minus one.
How do you get 2 n minus one?
See if n is a like there's a better way to look at it. If n is a power of two if n is equal to 2 to the^ k how will n how will this look like in binary?
You will have one followed by how many zeros followed by k zeros right? This is binary representation of n.
Yes, these are k zeros.
Okay. How will n by2 look like?
Just one shifted towards the right side.
This is how n by2 will look like. 1 0 0 0.
How will nx4 look like?
Just one again shifted towards the right side.
How will n by 8 look like?
1 0 0 0.
Yes, eventually when you do something like this, you say n + nx2 + n by 8 or yeah let's suppose n by 8 plus sorry nx 4.
So on pin one how will this look like?
If n is equal to 1 0 0 0 0 how will this value look like?
Can I say this value will look something like this?
One one one.
Yes, these are k + 1's. Uh k + 1 1's.
You initially add k zeros, right? These are k 0.
These are k + 1 1's.
Yes. What is this value equal to?
If you have k + 1 once, what is this value equal to?
Isn't it equal to 1 0 0 0 0 0 minus um 0 0 0 0 1 yes or no?
That is how you get this value. Right?
One second. It should be yeah correct.
So I think I have not drawn it properly.
I'll just draw it properly so that you're able to understand it. Um let's actually define what is the value of K here.
So you have 1 2 3 4 5 6 7 8 9 10 11. So K is equal to 11, right? So this should have k + 1 1's. These are 12 ones. 1 2 3 4 5 6 7 8 9 10 11 12 right these are k + 1 ones and this is uh this is one here and then followed by 12 zeros. So this is 1 2 3 4 5 6 7 8 9 10 11 12 followed by 12 zeros.
So what is this value equal to? This is nothing but 2 ^ k + 1 minus 1. And what was n equal to? n was equal to 2 ^ k. So this is essentially something like 2 n minus 1.
Is this clear guys? How we're getting uh n + nx2 + nx 4 + n by up till 1 equal to 2 n minus one when n is a power of two.
Okay, I hope this is clear. So how much space will this use now? Will it use n login? Okay, this is not clear. Okay, let do you know how to add numbers in binary chage?
If n is equal to let's suppose n is equal to 2 ^ 4, what is this equal to?
This is 16, right? So what what is 2 ^ 4? Uh sorry, what is n is equal n in binary? N in binary is 1 followed by four zeros.
Yes. Now what do you want? You want n + nx 2 + nx 4 so on up till 1. This is what you want.
Yes. So what will this look like? n is equal to 1 0 0 0. nx2 will look like will look like what?
0 1 0 0 0. N by 4 will look like uh 0 0 0 1 0 0. N by 8 will look like 0 0 0 1 0. NX 16 will look like and nx 16 is also equal to one by the way. So 0 0 0 1, right? If you add these numbers, what will you get? Wouldn't you get like wouldn't you get five ones? Yes. This will be 1 1 1.
What is this number equal to? This number is equal to 31 or rather it is equal to 32 - 1 which is equal to 2 and minus 1.
Okay. So yeah, so this is this is a binary way to look at it. You can also do it like finding out uh geometric progression. Uh you can find out the sum of geometric progression and you'll get the same value. Okay. Uh so what is the space complexity now? If we don't store the exact exact subarray in every single node, is it still n login or is it lower?
It is lower. It is order of n now because we're just storing 2 n minus one nodes and every node has how much memory? Constant space.
Is it clear to everyone how what exactly the segment looks like and how much space are we using? because if it was taking order of n square space, it it did not make sense to build it, right?
That is why we looking at the space complexity in that much detail. Okay.
Now, so number of nodes in a segment is how much uh if n is a power of two like if you if you know about trees, I I'm assuming you know about trees. Um if you have nodes, how many how many edges does it take to connect nodes in a in a tree? If you have nodes in a tree, how many edges does it take to connect n minus sorry nodes? It takes n minus one edges, right? So when you look at these internal nodes, there are n leaf nodes.
And then when you look at internal nodes, what are these internal nodes doing? So when you have a segment tree with just let's suppose four like when you have an array of four values, what are these internal nodes doing? Can can I say they're acting as edges?
So this is getting connected to this within with this node. This is getting connected to this with a node and then these both components are getting connected to each other with this node again.
So can I say internal nodes are something like edges edges in a tree which connect two nodes.
Yes or no? These are the actual nodes right? These are the actual nodes.
And then in order to connect these two nodes you are having this. In order to connect these two nodes you're having this. And then in order to connect these two components you're having this. So this is another way to look at it that you imagine this in the form of n leaf nodes. How many internal nodes will it require to connect all of them together which will be n minus one internal nodes. Right? So this is one way to look at it. You can also look at it in terms of binary that this has n space. This has nx2 space so on up till this has one space.
Right? It's the exact same thing. Is it clear to you how many number of nodes we have in a segment tree when n is a power of two?
Okay. Now let's look at what happens when n is not a power of two. Let's take an example.
Let's suppose n is equal to yeah let's suppose n is equal to 9.
Okay. So how will your segment look like? Your first node will contain what?
First node will contain 0 to 8.
Correct.
This is your first node 0 to8. What is going to be your first half and the second half? Use that formula which I told you.
What is going to be the first half and the second half in this uh segmentry? If this is the first node 0 to 8 0 to 4 and 5 to 8. Yes. Because how did you get four? Because you said s plus e by 2. Start is 0, end is 8. So s plus e by2 is four. So you have 0 to 4, right? And here you have how much? You have 5 to 8.
Okay. Now divide this further.
This will be how much? 0 to 2 and 3 to 4. Divide this further. This will be how much?
This will be uh 5 to 6 and 7 to 8.
Right? Divide this further. This will be 0 to 1 and 2 to 2. Divide this further.
This will be 3 to 3 and 4 to 4. This will be 5 to 5 and 6 to 6. This will be 7 to 7 and 8 to 8. Right? Now when you look at this level sorry this node is this node containing just one element? No we need to further divide it right. So when we further divide it what do what do we get?
We get 0 to 0 and 1 to 1 right.
Okay now think about it. If n would have been 16, if n would have been 16, how will your segment look like or let's look let's look at two cases when n is equal to 8 and when n is equal to 16 what happens when n is equal to 8 can I say my segment would have looked something like this that uh it would have been from here to here.
Yes. If n would have been eight, correct? If n would have been eight, this is how it would have looked like look like.
Okay. If n would have been a 16, how would your segment look like? Can I say each of these would have had children?
Yes or no? If n would have been 16, each of these would have been would have had children.
Yes or no?
Yes.
So when n is equal to 9, what can I say about it?
Can I say if n is equal to 9 the number of nodes for 9 is going to be greater than number of nodes for 8 but it is going to be less than number of nodes for 16. Can I say this?
Yes or no? Let me draw it out for uh for you guys for how will it look like for n is equal to 16 as well.
One second.
Yes, this is how it would have looked like for n is equal to 16.
each of these uh levels which ended here, these levels which these nodes which ended here, they would have not ended.
So what can I say about n is equal to 9?
Can I say the number of nodes in the segment tree for n is equal to 9, it is obviously going to be greater than the number of nodes for 8 because 8 is a power of two and it is obviously going to be less than the number of nodes for 16. Is it correct to say or not?
And what do I know about the number of nodes when n is a power of two? What do I know about this? Can I say the number of nodes in the segmentry for n being a power of two is going to be how much?
This is going to be 2 to 2 * 8 - 1 and this is going to be 2 * 16 - 1.
Does it make sense?
Is it right to say that if n is not a power of two, nodes for n will be less than equal to nodes for 2 ^ k such that 2 ^ k is the first power of 2 greater than n greater than or equal to n. Let's suppose is it right to say or not? Is this statement right?
Look at this. Number of nodes for nine is is less than equal to the number of nodes for the first power of two which is greater than 9.
Does this make sense?
Yes. So what can I say about number of nodes for n is going to be less than equal to what?
What are the number of nodes in the segment tree when the value of nodes is a power of two?
For this 2 to the power k like when when the array size is 2 to the power k how many nodes in the segment will exist we have 2 n minus one rule right so this will be 2 * 2 ^ k minus 1 make sense to everyone this thing 2 to the^ k is the first power of two which is greater than equal to n first power of two. Okay. And we know that what are the number of nodes in the segment when the num the size of the array is a power of two. We know that formula already.
Right? Now we also have to come up with a range on this. Right? Like we we just simply can't say 2 to the^ k like we'll just find out the first power of two which is greater than n and then uh you know talk about the space complexity. We also have to have a bound on this. What if this first power of two greater than n is just huge and it usually does not happen. See, try to understand this claim. Uh first power of two which is like let's say something like this.
2 ^ k is equal to first power of 2 which is greater than equal to n. Right? And the claim here is that 2 ^ k is bound to be less than 2n.
2 the power k is bound to be less than equal to 2n.
This is my claim that this is what happens. How many people think that this is true and how many people think that this is false? That the first power of two which is greater than n is bound to be less than equal to n. Let's take some examples.
n is equal to 9. What is the first power of two which is greater than 9?
16. Right? Is 16 less than equal to 18?
Yes. Let's talk about n is equal to 5.
What is the first power of two which is greater than equal to 5? 8. Is 8 less than equal to 10? Yes.
N is equal to 19. Let's suppose what is the first power of two which is greater than equal to 19?
32.
Is 32 less than equal to 38? Yes.
So with examples are you able to understand this that this usually happens like not usually but every time it happens that the first power of two which is greater than equal to n is bound to be less than equal to 2n.
Yes or no?
Do you want a proof for this or like is it intuitive?
like this happens.
It's like you can you can understand like this. See if like suppose you have 2 to the power k minus one and you have 2 the power k there is n where is n n comes here right? n comes somewhere here 2 the^ k is the first power of two which is greater than equal to n. So there has to be one number 2 ^ k minus 1 which is going to be less than n. Right?
Yes. The double of this comes out to be this. If you multiply by two if you double this this is bound to go beyond this. Right? This is bound to go beyond 2 to the^ k.
So you have 2 the^ k minus 1. You have 2 the^ k. n comes in somewhere in the middle. Wherever it comes we don't care about it. But when you double 2 the^ k minus 1 you get 2 the^ k. when you will double n you will get something higher than 2 to the^ k right so what did I know from here we knew that the number of nodes for n is less than equal to 2 * 2 ^ k minus 1 and this 2 ^ k is the first power of 2 which is greater than equal to n right so what do we know here we know that number of nodes for n was less than equal to two times 2 ^ k minus 1. And now we also know that 2 ^ k is bound to be less than equal to 2n. Therefore, if you take this as first equation and you take this as second equation, you can say the resultant is nodes for n is less than equal to 2 * 2n - 1 which means nodes for n is less than 4 n less than equal to 4 n - 1 which means less than 4.
Does it make sense guys that when n is not a power of two the number of nodes are less than 4n when n is a power of two the number of nodes are how much 2 n minus one but can I say in general in general for any Number of nodes for n is bound to be less than 4 n. This includes both the cases when n is not a power of 2 and when is when n is a power of two. When n is a power of two, this this value is how much? 2 n minus one.
When n is not a power of two, this value is 4n. So 2 n minus 1 and 4n 4n is a higher value. Therefore this this inequality basically considers both the cases that if you just take 4n nodes in your segmentry, it's going to be fine.
Does it make sense to everyone? What is going to be the size of our segment in the worst case when n is a power of two and when is when n is not a power of two.
Okay. So this is like I've already written it here. Uh when n is not a power of two and you find out the first 2 the^ k which is greater than equal to n then the number of nodes for n is bound to be less than equal to number of nodes for 2 to the^ k. We know that 2 to the^ k is bound to be less than equal to n. Therefore, number of nodes for n is bound to be less than equal to um like less than number of nodes for 2n. So, we can say number of nodes for n is less than equal to 2 to the 2 into 2 n minus one and therefore we get this inequality.
Okay. So, I hope the uh size of the segment is clear to all of you. Now, let's talk about doing those exact operations that we're concerned about.
We want to do a we want to update a single point in the array with some value and we want to perform range queries. Okay. So let's look at a point update.
What do we want to do when we want when we have to do a point update? A point update simply means that we have to go into our segment tree and you know like assume that our entire array has been updated with this update and then rebuild the segment tree right but we don't want to do those do that exact operation completely like we don't want to build the whole segmentry again we want to find out some optimization to do this right and the optimization is very clear like um let's suppose this is your segment before we move forward are you able to understand the structure. Now take some time and see if you're able to understand the structure. What does it mean?
This is the actual array that was given to us. And on top of that, we've built this segment.
So at index 0, you have a value of 0. In index one, you have a value of 27, 44, 93, 14, 40, 10, and 21. At this value, you basically add the left child and the right child. At this value, you add the left child and the right child. This one and this one. so on like this.
Okay, write a plus one if you are able to understand the structure. And going forward, we are going to assume that n is a power of two because it's easier to look at the tree. But um tell me one thing if you if you know that n is not a power of two. Is the is the tree still valid or not? The tree is still valid.
Okay, but just for simplicity so that you understand it very well, we're going to take n is n as a power of two.
although it will not matter. Okay. So, uh we want to now update the index 2 with a value of 46. So, what do we want to do? We want to update this value to a 46.
Okay.
So, we want to perform the update at this value and make it as a 46. Now, tell me one thing. Is any part of this segment going to change? Do you need to change anything here to make this update?
Do you need to change anything here to make this update?
No. Do you need to change anything here to make this update?
No. Do you need to change anything here to make this update?
No.
What do you really need to update then?
What do you really need to update? Can I say you need to update this leaf node?
You need to update this node which comes right above the leaf. Then you need to update this node which comes right above this node. And then you need to update this node which comes right above this which is the root itself.
So what are those exact nodes that are needed to be updated? Do we need to update the entire segment or only a very small set of nodes which we need to update?
We need to only update a very small set of nodes. Okay. And what are those exact nodes? Those nodes are the nodes which come from the root to that leaf node which need to be updated.
Okay. So first things first this part does not get updated.
This part does not get updated. This part does not get updated.
This part does not get updated. So what are those nodes which need to be updated? This has to be updated.
This has to be updated. This has to be updated. This has to be updated. And this has to be updated.
Right?
Now, if you look at it, the exact nodes that you need to update, nodes to update are what?
Equals to nodes from root to exactly Yes, these are the only nodes that you need to update. How many such nodes are there?
How many such nodes are there? What is the height of the tree?
What is the height of the tree? Height of the tree is login.
So the height of the tree is login. Can I say the number of nodes that I need to update is login as well?
Yes, correct. So the number of nodes that need to be updated are login.
We don't need to update the entire segment. We only need to update login nodes. Now another question is how do we reach that exact leaf node which needs to be updated.
You can start from the root.
When you come to the root, what is the range that the root uh like what is the range of elements that this root contains?
What is the range of elements that this root contains?
0 to 7.
0 to 7. What do you need to update? You need to update index two. Right?
So this index can only be present in one of the halves. Do you agree with this?
It can either be present on the left half or it can be present on the right half. Yes. So how will you find out whether it is present on the left half and right or the right half? You can find out the middle value. See what is going to be the middle for here. Middle is going to be 0 + 3 uh 0 + 7 by 2 which is going to be three. Which means that 0 to 3 comes here and 4 to 7 comes here.
What do you want to update? You want to update index two. So which half do you need to update? Left half or right half.
Which half does it is required to be updated? Left half or right half? Left half. Because the middle like the value that you want to update comes less before middle. So you want to update the left half. Okay. Now come here for here the middle is going to be what? 0 + 3x2 which is going to be two. So 0 + 3x2 will be 1 actually.
Okay. You want to update index 2. So index 2 is in the left half or the right half.
If the left half contains 0 to 1 and the right half contains 2 to three. Where will you go when you want to make an update? you'll go into the right half.
Okay? So you come here. Find out the middle again. Here middle is going to be 1 2 + 3x2 which which is going to come out to be two. So the left half is going to contain 2 to2 and the right half is going to contain 3 to 3. Where will you go? Left or right? You will go on the left. No. Once you reach the leaf node, it just simply means that you want to update the value. Yes. Once you reach the leaf node, it just simply means that you want to update the value. So this is what you will do. You will start from the root. You will find out the middle value at every point and you will either choose the left half or the right half.
It's like binary search. You go you go only in one of the halves. Right? So you come here, then you come here, then you come here and you update this value to a 46.
So this value has now been updated.
Okay? Initially this was 44. Now this value has been updated.
How will you update the remaining part of the tree? How will you update all the nodes which are from leaf to the to the root as you backtrack? So you can do it using recursion by the way. You will start with the root. You will keep it in memory. You will go here. You will keep this in memory. You will go here. You'll keep this me in memory. And you'll come here. Once you make this update, you will basically go back to the function which called it. Right? And once you are here, you can make an update. How will you make an update here? You will say that this value is equal to what? This value is equal to left plus right by two. So what will be the updated value here? Will it be 137 or will it be something else?
It will be 46 + 93 which is how much which is 139. So this will become a 139.
Okay. Now you come to this part.
What will this value be? This value will be a um 139 + 27 which will be how much?
You can just add a two here. So it will become a 166.
Right? Then you come to this node. It will be um left plus right by two which will be 251.
Are you all able to understand how did we do a point update?
Yes, we went down the tree to the leaf and then we just came back. We went down the tree looking for that exact leaf node which needs to be updated and then when we came back we kept at updating every single parent. This is how your final um point update will look like. So you went down and then you came back up.
Although if you make an update in the actual array, it's not really required.
Like maintaining the actual array is not really required after you have built the segment. Okay, this is not really useful now because anything that you will do now will be related to the segment and not the actual array. Okay, but just for simplicity, we have made this update here as well.
Let me know if it is clear to you how we are making the point update.
Okay, this clear.
Any doubts on this point update part?
Any doubts on this time complexity? Any doubts on how do we reach the leaf? How do we come back to the parent? We are going to look at the code but um logically if you're able to understand it's fine.
Okay, cool. I think you've understood point updates. Now let's come to range queries. How do we handle a range query in login time? How can we find out the sum of values from L to R in login time?
Okay. So before we move forward, I'll just grab some water. Um and until then, I'll just allow you to read this slide, ask these questions to yourself. Um and then I'll teach you the inquiries. Okay.
I'll just grab some water.
Okay, so I'm back.
Let's start with range queries. Now, um I am assuming you've read these questions. So yeah, let's suppose now you want to find out the um sum of values from index one to index five.
Okay, so what does this mean? We want to find out the sum of values. This this this this and this right. Okay. Tell me what are the what are the nodes which are which are irrelevant for us.
Is this part relevant for me? Um is this part of the segment relevant for me?
No, it's not relevant.
Right. So this is not relevant.
Is node 0 to 0 relevant for me?
Is node 0 to 0 relevant for me? No.
Okay. So this is not.
Now tell me one thing. If I know what is the sum of values from index 2 to three, is it stored somewhere? Yes. The sum of values from index 2 to three is stored here.
If I know this value, do I really need these values as well? Like do I need do I need these values?
Think about it.
If I know the sum of values from 2 to three, do I really need the exact values 2 and three or can I like as soon as I come to this node, I can just find out my sum?
Yes.
Similarly, when I look at 4 to 5, do I need 4a 4 and 5a 5 exactly or just having four to 5 completely is enough for me? Is 4 to 5 enough or do I need 4a 4 and 5a 5?
4 to 5 is enough. Yes. So, this is not relevant for me. This is not relevant for me.
Yes.
But otherwise, can I say all the rest of the things are relevant for me?
Yes or no?
Correct. All the rest of the things are relevant because when I need 1 comma 1, in order to reach 1 comma 1, I will have to travels from the root to 1 comma 1.
So therefore, this node is relevant.
This node is relevant. This node is relevant and this node is relevant.
Similarly, to reach this node, I need to go from the root to this. So this node is relevant. This is also relevant. And in order to reach this node, I need this node. So this is also relevant.
So can I say all of these nodes are relevant?
A node is relevant if I need its value or if I need it to go to some other node which is required.
Right? A node is only relevant if I if I need its actual value or if I need to go down if I know need to go you know below that node to find out those exact values right otherwise the node is not relevant for me.
Now think about it.
When you come to this U range 0 to 7, when you come to 0 to 7, what do you really need? Do you need 0 to 7 or do you need 1a 5? You need 1 to 5. So you need from here to here.
Okay. Now when you look at 0 to 7, you're standing on the root. You look at uh uh like 0 to 7. Is the entire range relevant? Is the entire range 0 to 7 going to contribute to your answer?
No.
Right. 0 to 7 entirely will not will not contribute to your answer. Right? So if 0 to 7 entirely will not contribute to my answer, can I say I will get the contribution from the left half. I will get the contribution from the right half. Add them together and give that as my answer.
Yes or no?
Yes. Okay. Now let's come to the left half. Left half contains the values from 0 to three. So it's goes from here to here. And let's look at the right half.
It contains values from here to here.
Only look at the left half for now.
What is the left half? 0 to 3. And what do you need? You need 1 to 5. So is 0 to 3 completely going to contribute to your answer or not or only a partial part of it is going to contribute to your answer 0 to 3 1 5 is 0 to 3 completely going to contribute to your answer of 1 to 5 no because it has that one node 0 comma 0 which not which is not required.
So when I'm standing on the left half I will again say that you know what my current node does not contribute completely to the answer. So I will go to the left and I will go to the right and try to find their contribution and result the and return the sum of contribution to my parent node. So I will come to this node. This node now contains 1 0 to 1. And this node now contains 2 to 3.
Okay. Look at 0 to 1. Is 0 to1 completely going to contribute to your answer or not?
0 to1 is not going to completely contribute to your answer. Why? Because it has node zero. 0 is not going to contribute. Only 1 comma 1 is going to contribute. So again you can do the same thing. Do one thing. Go to the um left half and go to the right half.
Now look at the left half. Is the left half contributing anything to your answer? 0 comma 0. What do you need? You need 1a 5. And what do you have? 0 comma 0. Is 0a 0 going to contribute anything to your answer?
Yes or no? No. 0 is not going to contribute anything to my answer. So what I will do is I will return a zero from here.
I will return a zero from here. That it does not contribute anything to my answer. I will not go further down. My current range does not intersect at all with the required range. Therefore, it contributes nothing. What about 1 comma 1? Does 1 contribute to my answer? Yes, it contributes completely. 1 comma 1 is completely inside 1 5. Therefore, it contributes completely. So, I will return the value which is present there which is a 27.
Okay. Now come to 2a 3. Does 2 3 contribute anything to my answer? Yes. 2 3 completely contributes to my answer.
Therefore, I don't need to further go down looking for a bet, looking for a contribution. I can just simply return 137 up. Does it make sense, guys?
Right from here, I will just return a 137 up.
And from this node, I saw that my left half contributed zero and my right half contributed 27. Therefore, I will return the sum of it, which will be a 27 as my total sum returned.
Right? And now from this node I I know that my left half contributes 27, my right half contributes a 137. So what will I return? I will return the sum of these which will be a 164. Yes.
Okay. By the way, why did I return zero from here? I returned a zero because it contributed nothing. I did not return its value in this case. I returned its value which was a 27. In this case, I returned its value which was a 137.
Okay. Now let's come to the right half.
3A 4. Does 3a 4? Sorry, not 3A 4 7. Does 4a 7 completely contribute to my answer?
Does 4 7 completely contribute to my answer? No. 4 7 has some part which is not contributing which is 6 to 7. 6 to 7 does not contribute anything to my answer. Right? So what I will do is I will go to the left half and the right half and I will ask for their contributions. Okay. Let's come to the left half. Let's come to the right half.
Does the left half contribute any anything to my answer? Yes, it contributes completely. 4A 5 completely lies within 1 125. Therefore, I will return the value which is present here which is 54. So, I will return a 54 from here. What about the left half? Does the left sorry right half does the right half contribute any anything to my answer? No. So, I will return a zero from here because 6A 7 is not intersecting with 1A 5. Right? So, for this node left half said 54, right half said 0. So, I will return a 54 from here. Now for this node I will say left half contributed a 164 and right half contributed a 54. So this will be a total value of 218.
Are you able to understand how did I get my range query? How did I get my answer for the range 1 to5? You can try adding these values. It will come out to be 1 218.
Are you guys understanding? I don't see any response. Are you able to make sense or are you not able to make sense?
Yes. I'll completely like uh you know remove all the text that I've written here and I'll write the exact values that I'm returning from every round.
Okay. So that it is easier for you to visualize.
Okay. So I started with the first uh this part. For this I went on the left left side and the right side. For this I went on the left side and the right side. For this I went on the left side and the right side. From the left side I returned a zero because it contributed nothing to my answer.
From the right side I right side I return a 27 because it contributed completely to my answer. There from this node I returned a 27. Left half plus right half value returned from left value returned from right. for this node. When I reach this node, it contributed completely to my answer.
Therefore, it did not make sense to go further down. So, I returned 137 from here.
Okay. Now, for this node, I looked at the left value returned from left, value returned from right. I added that and returned that. So M is saying by the way are are are there problems where understanding this part of segmentry helps or no it's important that you understand this part because it's not like segment is not like an algorithm it's a data structure when you're using a data structure which is heavily used in a lot of applications you have to understand its internal working you cannot treat it as a blackbox so there is something known as a fenit tree as well so fenit tree does not have any applications as such it is used in a single single case. So therefore it is not required for you to understand the internal workings of the fenic tree. U when you look at dystra for example the shortest path algorithm for graphs. Do you really need to understand how it works internally? My my saying is no because it's a standard algorithm every time you have to use it. But when you look at a segment you'll have to like unless you understand its internal working you will not be able to modify it for various different types of range queries. Here the type of range query that we're dealing with is go to a particular node in like go to a particular index in the array update that value and get me the sum of values in a range. You can also have um you can also have a segment tree where or you can have a problem where you want to find out the gcd of all the values. You want to find out the gcd of all the values from L tor not just the sum and there if you don't understand how what will you return from every node how will you combine the values from every node you will not be able to solve it right that is why you you cannot treat a segment as a black box now for this node you look at the left half what is returned 27 look at the right half what is returned 137 so you return 164 to the top okay now coming to this part uh for this also you went left and you went When you went to the left part, you realized that it is a complete overlap.
4a 5 is completely contributing to my answer. Therefore, I did not further go down and I returned a 54.
For the right half, I realized that it is a no contribution like there is no contribution to my answer. So, I returned a zero.
Now, for this node, I returned basically a 54 to the top. And for this node, I know that left half returned 164, right half returned 54. So, I have a value of 218.
Is it clear? How did we do this range query to all of you?
Okay. So, here's a visual of the same like we start from 249. Let's suppose we're going on the left part. So, we went to 164. Um, yeah. Then we I think this is not drawn properly.
Yeah. Anyway, so we started with uh 0, 7, we went to the left half. Then from this left half, we went here and we went here. Right?
From here, we went here and we went here. Right? So, yeah. And similarly, from here, we went like we returned a zero from here. We returned a 27 from here.
So, therefore, we returned a 27 from here.
And we returned a 137 from here. We returned a 164 from here.
And similarly on the right part you went here. You went here you went here. From here you returned a zero. From here you returned a 54. So therefore from here you returned a 54. And finally from here you returned a 54 + 164 which is be which will be a 218.
Okay. Now when you look at range query there are three things that matter.
Okay. So first case is this where this is your segment node.
So let me write it here.
Okay, first case is this that um your segment range is not contributing anything to your query range.
Okay, let's suppose your query range looks like this. The blue part is query range and the red part is one second.
Red part is segment range.
What do you do in this case? Do you go further down the segment or do you just return zero from here?
What do you do? If you have a query range and if you have a if you have your current node segment range, if the current segment range does not contribute anything to your answer, what will you do? Will you further go down the segment or will you just return zero from here?
Because obviously the ranges below the ranges below this range will look something like this. This this if this does not contribute anything to your answer, can any of the can any of the ranges below contribute anything to your answer? No. So in this case what do you do? You return a zero.
Okay.
This is case one. Let's look at case two.
This is your segment um range. Let's suppose and sorry this is your node query range and this is your segment range.
What happened in this case?
Is your segment range contributing anything to your answer? Yes, the entire range is contributing to our answer. So what do we return in this case? We return the value that is present on the segment node. we return that value because if this range is contributing completely I know that all the ranges below this will also contribute completely right so do I need to go down that segment node no I can simply return the value that is present in that segment node so return okay and the third case when you have a partial overlap. Let's suppose this is your um query range and this is your segment range.
What happens in this case?
In this case, I know for a fact that my entire segment node does not contribute to my answer, but I know a a partial part of it contributes to my answer.
What do we do in this case? In this case, we we need to go further down the tree, right? Because we we don't have enough information right now to say what is going to be that exact value which contributes to our answer. So, I will go to the left half and I will I will go to the right half and I will say what is the contribution of the left half? What is the contribution of the right half?
Add them together and return that. So what I will do in this case is I'll go down and I'll say return left plus right contribution.
Are you all able to understand this?
These are the only three cases that can happen.
So case one is uh no contribution.
Case two is full contribution and case three is partial contribution.
When there is no contribution, you don't go down the tree. When there is full contribution, you don't go down the tree. When there is a partial contribution only, then you go down the tree.
Let me know if this is clear to all of you and then I'll explain how does this work in login time. Why does this happen that it when you do this it works in login time?
Are there any cases which which you think what if blue line is a subset of the red line? Very good question. I was hoping somebody would ask this.
What if you have something like um blue line from sorry from here to here and the red line from here to here?
Tell me what is this? Is it any one of the three cases 1, two or three?
Yes, it is case three because the segment range is contributing partially.
See the first type of uh uh the first type of case is where the segment range contributes nothing to your answer. The second case is where the segment nodes contributes completely to your answer.
The third case is where the segment node contributes partially to your answer. In this case, what do you think? Is the segment range contributing completely to your answer? No. Because it has some part which is not valid. It has some part which is not valid.
Right? Is this is this like a no contribution? No. Because there is some part which is contributing.
So what does it mean? What is it? It is the third case.
It is a partial overlap. Are you able to understand Kushell?
It's a partial overlap.
Okay.
So the three cases are as follows.
Um when there's a no overlap you have segment start um like you can call it as left like I'll say left and right is um start and end is segment start comma end is segment and l comma r is query.
Okay. So when do you have no contribution?
When your start is greater than R or end is less than L.
Yes or no? You have a segment range which is S to E and you have a query range which is L to R. When will there be no overlap? When the start of the segmentary range is beyond R or when the end of the segmentary range is before L this is no contribution.
What is case two? Complete overlap.
Complete overlap means that start is greater than equal to L and end is less than equal to L. Sorry, end is less than equal to R.
Right? The segment range starts greater than equal to L and it ends before R before or up till R. Only then the segment range will contribute completely to your answer. Right? So this is complete contribution and the other one is just partial. If none of these two cases happen, it's obviously a partial overlap.
The third is like if you say this is if this is else if then this is the else condition. This is partial overlap. You don't need to write it as such. It's obvious that this will be a partial contribution.
Tell me if this makes sense that how will you find out these conditions?
Okay. U now how many people feel that in the worst case we might we might just end up visiting a visiting too many nodes. How many people feel that like intuitively it makes sense right that if you're doing something like this in the worst case we might just end up visiting too many nodes.
Yes.
>> Okay.
Oh, one second. I have somehow lost my nib of pencil. Just give me one second, guys. I think I've dropped my pencil nib. So, I'll have to find it.
>> Yeah, I I found it luckily. uh otherwise you would have ended the class. So yeah uh okay let's uh let's move forward. So yeah first question is when do you go down?
When you're standing at a node when do you go down?
When you're standing on a node when do you go down? Only in case of partial overlap. So we can write we only go down a node to its children when it is a partial overlap.
Right? Now see our u our time complexity or our number of nodes that we resetting can I say is is like directly proportional to the number of partial overlaps that we'll have because for complete overlap and for no overlap we just simply returning we don't we don't do anything in those cases right so can I say my time complexity is like proportional to partial overlaps the more number of partial overlaps we'll have the more number of nodes we'll visit the less number partial overlaps we have the less number of nodes we'll visit.
Okay. Now I'll give you a claim and then I'll prove it.
For every level we will not visit more than four nodes.
So right now don't don't try to uh verify whether it is correct or not. I I'll actually prove it. But tell me one thing if this claim was correct. If for every level I can somehow prove that the number of nodes we will visit in the worst case is less than equal to four.
What will be the time complexity then?
Four login. Yes. If this was correct the time complexity will be four login.
Number of levels are how many login?
Number of nodes you're visiting on every level. Maximum is four. So this will be four login.
Right now let me prove why this works.
See uh let's draw some ranges here.
Okay.
This these are like secondary ranges.
Let's suppose first range, second range, third range.
Okay, these are segmented ranges. Fine.
Um, now when will you have a like when you start from the first node? This is the the top red line is the first node in the segment tree. Okay. Uh when will you have a partial overlap? If your if your query range is from here to here, will this in will will this be a partial overlap or will this be a complete overlap?
If your query range is like this, will be will this be a partial overlap or a complete overlap? It will be a complete overlap. So this is a useless case. It will not end up visiting many nodes. So we'll not consider this case. Okay.
Another case is that if it is a prefix, if the query range is a prefix, what will happen in this case? Or let's suppose if the query range only lies in the first half. If the query range only lies in the first half, what will you do? It is a partial overlap. So you will go on the left side, you will go on the left side and you will go on the right side. But when you go on the right side, will it be a complete overlap, partial overlap or a no overlap?
When you go on the right side, it will be a no overlap. So what will you do?
Will you further go down the tree or will you return?
You will return.
So when the query range is present in the left half, it is useful. Is it useful for us or is it not useful for us? It's not very useful, right? It's not going to hit a lot of cases. So query being in the first half is not very useful. What about the query being in the right half? Can I make the same argument that if the query is present completely in the right half then the left half is going to return left half is not going to go further down right does it make sense if the query is completely in the right half it will not go down the left side right it will just return so what is our query which will actually hit a lot of cases can I say something which is present in the middle something here a query which is present in the middle will make sure that the right half goes down and also the left half goes down.
If a query is only present in one of the halves like left half or the right half, it will just only make sure that one of the halves go down. The right half just returns or the other half just returns.
Okay, now when the query is in the middle only then we'll hit our worst case. Okay, let's imagine our query being here.
Okay, if our query is here, what will we do? We'll go to the left half. We'll go to the right half.
Okay. Now look at the left half.
Look at the left half.
If my query range is from here to here, like it ends here, it ends here and it ends here.
When I'm standing here on this particular node, I will go to both the sides. I will go to the left and I will go to the right.
Yes or no?
I will go to the left and I will go to the right because it's a partial overlap. This query with this range is a partial overlap. So I will go to the left and I will go to the right. But will I go down further on the left side or will I just return? Will I further go down on the left side? Left side or will I just return?
I will just return. Right? Because the query is from here to here only. So this part is going to return.
Same for the right side. If the quer is present till here, I will come here and I will come here. But from the right side, I will return right because it's not contributing anything to my answer.
Correct.
What is required for the right side to not return? What is required for the query from the query for the left half to not return? Can I say the query will have to be like this?
Only when the query is like this.
Only when the query is like this, it it goes up till this point. Only then the left half will not return. Yes or no?
Now when you come to the left and you come to the right, will the left half return?
Will the will this part return or will it further go down? It will go down. It will not return. But what about this part? Will it now further go down or will it just return? It will return because because it's a complete overlap.
Are you able to understand what did I just say?
See only focus on the left part.
The query goes from either here to here.
On the right side we don't care till where it is coming. On the right side we don't care. Okay. This black part is is the query range. The right half of the query I'm not concerned about. I'm only looking at the left part. If the query lands still here, if the query lands till here, what can I say? Can I say the left part will return when you're standing here? The left part will return yes or no. If the query goes till this point, in order for you to not make the left half return, the query will have to go further will have to go further right till here.
And if the query goes beyond this middle point, what will happen? This will become a complete overlap and this will return.
Can I do something so that both of them they don't they go down? Can something like this be done that both of them go down?
No, it cannot happen.
Why can't it happen?
Again look at it.
There are two things that can happen.
Don't look at the right half of the query for now. Only look at the left half of the query. Let's suppose this is query number one and this is query number two.
Okay.
What happens for query number one and what happens for query number two? For query number one, this returns.
For query number two, this returns.
Are you able to understand?
For the first type of query, the left half is bound to return because it's a low overlap. For the second type of query, the right half is bound to return because it is a complete overlap.
So what can I say about these two nodes?
Can I say only one of them can go further down? Both of them cannot go further down. Can I say this?
Yes or no?
Only one of them can go further down.
Okay.
And now can are you able to see that the same argument will hold for this level?
That only one of them will be able to go down not both.
We can take again we can take an example. See if I say that the quer is from here to here.
Okay. What will happen in this case? You will come here. You will go down here.
Here. This will return. This will further go down. When this further goes down, can I say this will return?
Yes or no? If the query is still here.
Yes. Okay.
What if the query is from here to here?
If the quer is from here to here, can I say this will return?
Yes.
Okay. What if the query is from here to here?
Then I will say this will not return.
But this will return. This is not useful. Now this will go here and here.
And this will return again. Only only one of them is valid. Only one of the node is valid. Right? What if the queries from here to here?
If the quer is from here to here, this will further go down but this will return.
So are you able to see the pattern here that no matter what happens only one of the nodes can go further down and when one node goes further down how many children do you end up visiting? You only end up visiting two children. So two children on the left half and two children on the right half every single time. How many children can you end up visiting on every level? Four.
If you want to understand this again, let me know. But um the whole idea is that a query range is always continuous.
Okay, this is the main crux behind it. A query range is always continuous because of which what happens is that after you go down the first level after you go down the first level the left part becomes a suffix and the right part becomes a prefix. See if this is your query range. Okay, if you only look at the left part, if you only look at the left half here, can I say left half is nothing but a suffix because the query is always going to go from here to here. It will always start from this left. It will always start from the midpoint and will go toward the left side. Similarly, when you look at the right half, the query range is always going to start from middle and is going to go towards the right. So, it is always going to act like a prefix.
Yes or no?
As soon as you go down the first level, the query range becomes either a prefix or the suffix for the left and for the right.
And when it becomes a prefix or a suffix, it makes sure that when you're going down, two nodes cannot go down.
Because if let's suppose the left part goes down, then the right will be a complete overlap. And if the right goes down, then the left will be a no overlap.
Are you able to understand all of you here? How for every how for every level you will not end up visiting more than two nodes on the left and more than two nodes on the right. In total it will be more not more than four nodes in total.
Write a plus one if you're able to visualize this. Now why you will not end up visiting more than four nodes at any level.
Okay. I only see a plus one from one person. What about the rest of you? You not understood.
Okay, now I see two plus ones.
Who has not understood? Write a minus one and tell me if you've not understood. We can go over this again.
Still absorbing. Okay.
See if you want to observe I'll give you two cases and you think about those.
Okay, this is the half here.
How long is today's class? Just I think uh maybe 10 more minutes, right? Uh we can discuss the code in the next class, but I think that that would not be really useful. Uh I think we we'll go for 30 more minutes then. I think it will be a long class. Okay, we we'll look at the code also in today's class. So for absorbing this, I'll give you two examples. Uh don't look at the right half of the query because the right half is going to be exactly same.
Only look at the left. Okay, let's suppose the query is from here to here.
What happens in this case? How will the tree look like? Like how will you go down the tree for this node? It since it is a partial overlap, you will go down.
You'll go here and you'll go here. Okay.
Now, uh I'll just also draw it out properly so that it's easy to look at.
Now for this node, you will go down here.
You will go down here. Will your left child go further down? Will you further go down from here?
No, because it is going to be a no overlap. So you'll return from here.
Look at this node. Will you go further down? Yes, because it's a partial overlap. So you'll come here and you'll come here. Look at this node. Will you go down further this node?
No. Why? Because it's a complete overlap.
So you'll return from here. Look at this node. You will go further down because it's a partial overlap. So you'll come here and you'll come here.
Will you go further down from this node?
No. because it's a no overlap. So you'll return from here. Will you go further down from this node? No. Because it's also complete overlap.
You have to notice one thing which is that for any level only one of the child has the potential to go down. Both the child don't have the potential to go down. Why? See if this is the left child. Let me draw another thing. If this is the left child and if this is the right child. Okay, if this is your query range, now the query can either like query can only be a suffix. Okay, so the query can go from here to here or the query can go from here to here. This is first type of query. This is second type of query. For the first type of query, what will happen? The right child will go down but the left child will return. Why? Because it's a part it's a no overlap for the left child. For the second query, the left child will go down but the right child will return why because it's a complete overlap.
Are you able to understand that among these two children only one of them can go down?
Similarly when you go down further when you go down the tree further you will realize that among like see out of these two one and like let's call it A and B.
Let's call it C D E and F.
Among A and B only one can go down.
Let's say A is going down. So if A goes down, B is completely returning. So E and F are not valid. These are not valid. Among C and D, it will be the same argument that only one of them can go down.
Yes, Ada, are you able to understand this? Among C and D only one of them can go down. Yes. If you take the other case, if B is going down and A is returning, then C and D are invalid.
Then among E and F only one can go down, right?
So if you have like if you further have smaller children like G and H um I and J let's suppose so what will happen now if among E and F only one can go down if E is going down then I and J are invalid right you will only end up visiting G and H and among G and H also now you can only visit like you can only go down one one of them same for the case when E is not valid when E is not valid only F will go down and G and G and H will not be valid among I and J again you will have the same argument that only one of them can go down. So when you look at the left part of the segment tree this is the left part of the segment tree only two nodes can be valid at any point.
Similarly on the right side the same argument will hold that only two nodes can be valid. So in total in a range query only four nodes can be valid at any level. Therefore the time complexity is 4 into log.
Clear to all of you how we can do a range query in login time. Now so this is login. How to reach the relevant node? We know that there can be three cases. What happens when the current range is completely useless?
Return zero.
Return.
What happens when the range is completely useful? Sorry. When it is completely useful or completely useless, you return both cases.
When there's a partial usefulness, you go down.
Okay. How many nodes can we explore at any level? Four. Max four. What is the time complexity? Less than equal to four login.
Okay.
Now comes the part how do you build the segment? We've looked at how can you do a range query, how can you do a point update, how can you now build a segment tree.
See, it's not very difficult to say if you have this as your array.
For simplicity, we'll again take four like n as a power of two.
Okay. Let's suppose these are the values. So how you will build the segment is you will look at node one.
You will start with the top node. Okay.
This is node one. Node one is going to store what values? This is 0 1 2 3 4 5 6 7. Node one is going to store which values 0 to 7.
So this is node one. Okay. Node one is going to have two children. And how will you define those two children? Left half is going to be 2 * node and right half is going to be equal to 2 * node + 1.
We'll see how this can be done. So do you know how to define the ranges of the left and right?
What will be the range of the left half and the right half?
It will be 0 to what? 0 to 3. Why three?
Because we say m is equal to s plus e by2 or let me just write it properly then you'll be able to understand it.
First node entry is equal to root is equal to node one.
Okay. Now what is going to be the range of the first node?
Uh let me write it here.
What is going to be the range?
0 to n minus one for a general array.
Right?
What about the left and left child? left and right side.
So left is equal to um 2 * node value right is equal to 2 * node value + 1. Okay. The range of the left will be start to mid and the range of the right will be mid plus one to end.
Okay. So this is the case where if node has start to end as the range.
Okay. Now let's try to look at the construction. Are you able to understand this much at least?
How are we naming the nodes and how how are we defining the ranges?
Yes.
So first node will be what?
0 to 7. In our in our array here for this array, our node will be what? 0 to 7. What will be the node number? Node number will be one. Okay. Construct the left and right of it. What is the left?
0 to 0 to mid. What is mid? Mid mid is start plus end by two which is three.
What is this? This is 4 to 7. Okay. This node will be two. This node will be three. Okay. Further go down this you'll have 0 to 1 and you'll have 2 to 3. 0 to 1. What will be the node number?
What will be the node number for 0 to 1?
It will be four. It will be 2 into 2. So this will be four.
What will be this? This will be five. 2 into 2 + 1 5.
This will be 4 to 5. This will be 6 to 7. Node number here will be six. Node number here will be seven.
Okay. Further go down this.
Okay. What will be the node number for this? 0 2 into 4. This will be 8. This will be 9. This will be 10 11 12 13 14 15. Here I'm only writing the node numbers. Okay. These are not the value of the node. Are you able to understand this? This is node number.
Number of the node.
This is not the value exact value. Exact value will be determined from the value in the array. What is present in the array. Based on that we'll build the segment.
So before we build the segment are you able to understand how will the structure look like we'll start from the root we'll number it as one we'll look at the left and the right we'll continue going down and how will you find the node number for any node we'll look at its parent and just like if it's a left half we'll multiply by two if it's a right half we'll multiply by two and add a one okay now once you reach the leaf nodes you will look at the actual array what is the actual array 10 so We'll put a 10 here. We'll put a two here.
3 4 2117.
Okay. Once you reach the leaf node, you can just say that the exact index where you are that is the uh like that is the value that you will get from the array.
Okay. Talking about any internal node, you will get its value by adding the left child and the right child. So this will be 12. This will be seven. Let me use a different color. This will be 12.
This will be seven. This will be three.
This will be eight. This will be 11.
19. And this will be 30.
So we'll we'll build it using recursion.
We'll start from the root node. We'll continuously going keep going down. And when we are coming back up, we'll actually calculate the values of the internal nodes.
Does that make sense guys?
Where will we store these values? This 7, this 3, this 8, this 11, this 19, this 30, 12, 10, 2, 3, 4, 2, 1, 1, 7.
Where will we store these?
You remember in the beginning I asked you like about the number of nodes in the segmentry. Why is it important?
Because the values of these nodes, you'll have to store them somewhere, right? So, you can store them in an array. That is why these numbers are important. What is the node number? This node number will tell you where are you storing the um actual value.
Okay. So we'll just look at the code.
It'll it'll make sense. Right now it'll be a bit abstract to explain this but we'll just look at the code and and you'll be able to understand. Okay.
Should we look at the code?
What define first of all let's answer these questions. What defines a node uniquely?
What defines a node uniquely? In our case either you say node number or you can say it's start and end range start and end uh points.
This defines a node uniquely. Okay. Uh so when you're building the segment it it looks something like dynamic programming as well. Why? Because when you're calculating the value of your current node how are you getting it?
You're saying that the value of the left plus the value of the right. Doesn't it look something like dynamic programming?
See it's not actually dynamic programming. This the answer for this is no.
What is dynamic programming and what is divide and conquer?
Divide and conquer says that you have a big problem you divide it into small chunks and you have a relation between the smaller chunks to get the answer for the bigger chunk. That is divide and conquer. Right? What is dynamic programming? You make use of dynamic programming when your divide and conquer problem has multiple overlapping subpros.
Do you remember this statement that I made in the in probably the first class of level four?
Dynamic programming is when you have divide and conquer with overlapping subros. Do we have overlapping sub problems here? The answer is no. Every sub problem is unique.
Every node is unique, right? In the segmentry. It's not a it's not like a it's not a repetition like Fibonacci. So we don't have divide and conquer. Sorry, we don't have dynamic programming, but we do have divide and conquer here.
In divide and conquer, we don't store the sub problem solution. No, that that's not the idea. So uh dynamic programming is not about storing the answers of the sub problems. Dynamic programming is about identifying that you have overlapping sub problems in a divide and conquer problem.
What is divide and conquer? Divide and conquer is breaking a big problem into smaller chunks. Divide dynamic programming is not it does not talk about storing anything.
Dynamic programming only says that okay you have overlapping sub problems so you store the information. Here we are storing the information because like it's not because we have overlapping sub problems that we want to solve the same problem again and again. Dynamic programming is used when you want to solve the same sub problem again and again and so you store it. Here that is not a problem. Here we need that particular sub problem. It's not like you're going to solve it again and again. Okay. So it's not divide and conquer. It's sorry it's not dynamic programming. It's just divide and conquer.
Um can we define each node with a unique integer? Yes. We just saw how we can do it. How to file find the child and parent of a particular node. Um so how will you find the child of any node? If uh let let's suppose you have x. So left will be 2x right will be 2x + 1. And if you have x the parent of x will be just xx2.
So if you take x 2x + 1x2 you'll get x.
If you take 2x2 you'll get x again.
Okay. How to store the information for every node? You'll use an array for this.
What is the time complexity to build the tree? We'll see. We'll see this. Okay, let's look at the code for this. Now, I'll just uh stop sharing for a minute.
I'll share my Sublime Tech screen.
Don't we have overlapping sub problems?
We have to calculate the sum of sub area again and again.
No, no. So, I I'll actually come to this u in a minute. Are you able to see my uh uh what do I say? Sublime text. Sublime text screen.
Yes. Okay. So, we have an array. Let's suppose um or let me do one thing. Let me share the screen instead. And I'll move my sublime text here. I hope you're able to see this. Yes, just confirm once.
Okay. So, uh I just write here.
This is where I take in the input of the array.
Okay. Next, now I need to define my um what do I call this? I think there's some problem.
It's not taking the tab correctly.
This is weird.
I'll just take in the array here.
There's some problem with the tabbing. I guess let's make another um array which will be like the segment array. Okay, let's call it SD. How many nodes will the SD have? How many nodes in the worst case do I need? Four m right bottom right corner of sublime has tab options. Okay, that's fine. Like we can manage without it.
Are you able to understand why did I write a foreign here?
Yes.
Okay. I'm assuming you understood this.
Let's make a function build which will take the start, the end and the node number. Okay. And what I'll do is I'll make these arrays also global so that I don't have to pass them again and again.
Let's say a size of,000.
This is like 400,000. Right now I'm assuming the value of n is going up to,000. If you want even higher, you can make a higher up. Let's make a higher value. Okay. Let's make a function void build. It takes a start. It takes the let's say s in e and it takes node number. Okay, let's call it index. This will be the index of the node in the segmentary.
Okay. Now, uh first thing is that if you've reached the leaf node while building, if you reach the leaf node, so you can say if s equals equals to e.
When s equals equals to e, what does it mean? It means that you have just a single um single value in your current node. So there you can say that SGT at index equals to a of this.
This will basically store whatever is present in the array at that index into the segment and then you return.
Otherwise, if it is not a leaf node, what do you do? You find out the mid as S plus E by 2, right? You build the left half. You say that the left half is going to go from S to M. The index will be 2 into index.
Build the right half which will be from M + 1 to end.
uh index will be 2 into index + one. And then how do you combine the answers of the left and the right to get the answer of your current?
How do you combine the answers of the left and right to get the answer of your current?
Can I say SGT at index equals to SGT at 2 * index plus SGT at 2 * index + 1?
Is it correct to say this?
Once I have built my left half, once I've built my right half, I can just say that the value at my current index is equal to value of my left plus value of my right.
One second.
One second.
Is the build part clear to you?
Okay, let's write down the query part now or let's write down the update part.
Void update.
So you'll have S, you'll have E, you'll have index. Uh you'll get a L, you'll get an R. Sorry, you'll get the index um update index and you'll get the update value.
How can you do this? Again, if you reach a leaf node, if S equals equals to E, what does it mean here?
When you reach a leaf node, it simply means that you have reached that exact index in the array which you want to update. Right? So now you can simply say SD at index equals to update value because you have reached that exact particular index in the array and also the exact index in the segment which needs to be updated. you just updated and return here.
Otherwise, when you're at an internal node, what do you do? You'll find you find the mid, right? And now what do you do? You update only one of the halves. How do you find out which half needs to be updated? You can say if mid is greater than equal to update index, it means where do you want to update? Do you want to update the left or the right?
If mid is greater than equal to update index, which part of the segmentry would you want to update? Left half or the right half?
Left half. Correct. So we'll say go update the left half. S comma mid comma 2 * index comma um update index update value.
Yes. Else else you will go on the right half. So you'll say mid + one end two times index + one update index update value.
Okay. Once you have made the update on whichever side was required left half or the right half what do you do? Like you have gone down the tree now you're coming back up. What do you do? You update your current value. How do you update your current value? By adding the updated value of the left and the right.
So you again do this. SDI index equals to SDI. Just copy this and put it here.
Do you think this will update my entire segment?
Yes. Okay. Let's write down the query function as well. Now what are the three cases? No overlap, complete overlap or partial overlap.
What happens when you have an overlap?
If s is greater than r or or n is less than l in this case what do you do? You return zero.
If you have a complete overlap, how do you find out if it is a complete overlap? You can say if s is greater than equal to l and or you can say and and e is less than equal to r. In this case, what do you return? You return sgdr index the value present in the segmentary node. And if it is a partial overlap, what do you do? to find out the mid and you say if uh like you uh say int left answer left contribution let's say query on the left side s comma mid comma 2 * index comma l comma r and similarly you say int write contribution and what do you return? You return the left contribution plus the right contribution.
Take some time to understand this.
Can you show the build part once again?
Yes, this is the build part.
any doubts in this build part.
See there is something that you can do.
You can say um int left child which is going to return two times index. This way you will not make any typos. You can say try child you can return two times index + one. So when you do something like this instead of passing two times index and all of these you can just simply say left child index right child index.
Similarly here you can basically make this um condition at all the places if you want.
Line 96 there's some problem. Yeah let's call it M. Let's make this also M.
or let's keep it as mid only. Mid is more easy to read.
This is M.
Yeah, correct.
This way you'll not make any errors in this. Like sometimes you want to write two into index and sometimes you write two into index plus one. It happens a lot. So it's better to modularize the code.
There's another modification. Um it gives compilation error in passing one function inside another.
Where are we passing one function inside another?
This we're not passing a function.
We're passing the value returned from the function. Here you can do another thing. You can say int combine children So now you can see something like this um combine children.
So this way you don't have to write the combination logic every time.
Right.
Tell me if any of it is unclear. I'll write down the time complexities. built part is order of n. Are you able to understand why order of n?
Imagine this as a dfs.
You have n two nodes in that tree. Every tree you visit once and you're basically doing a dfs. From every node you're going to it children, right?
So order of n for build, order of login for an update.
If given the node number, can I find its left and right limits without access to its parent?
Um, technically you can like you can write a function which can store all of these. Um, for every index you can store the left and right. One of the ways is this. But there might be a formula as well which you can come up with because there's a unique um unique mapping right every index has a unique mapping to its left and right. So you can do it but um I am not sure if I can think of it really quickly right now. I haven't come across anybody using that.
Okay, tell me if this is clear to all of you. How do you build a segment tree? Um what is the time complexity of each of these actions and um how does the code look like?
So now if you want to handle queries you can do something like this.
You want to update at 0 n - 1 1 and you want to update index index minus one. So I'm writing index minus one because like it is input is given in one based index and whereas we are building the segment on zero based index and if you have type two then you say int L comma r see out query 0 comma n - 1a Okay, any doubts on this or should we wrap it up?
If we are using zerobased indexing, won't the children be 2x? So, uh the the segment indexes are one based.
Basically, the node uh the top node is node one. The children are node two and three. But when we're looking at the indexes in the array, right? Indexes in the array are zero based.
So, array is zero based indexed, but segmentry is one based indexed.
Okay, that is it guys. Um, can you take the DP question asked earlier? Yeah. Can you can you repeat what was the DP question? You said that it looks like dynamic programming, right?
Somebody said that it looks like dynamic programming.
Okay. So Ada is saying don't we have overlapping sub problems? We have to calculate the sum of a subarray again and again. In this case, can't it be DP um okay like if you look at it that way then yes it is dynamic programming that you want the answer for a particular problem again and again. Um and that is why uh you know you can call it dynamic programming but technically it is not that.
So yeah what Adv is saying that the build function is not DP which is correct because in the build function we don't have any overlapping sub problems right and now the query part is looking like DP because we are making we are reusing some answers right we are reusing the answer of a um let's suppose we look at look at a subar when the when the subar is a complete overlap we don't go down further we don't further go down the tree we just return that value which is present right that is how you're calling a dynamic program but when you look at it that way even prefix sum looks like dynamic programming, right?
When you look at a prefix sum, would you call a prefix sum dynamic programming?
No, because it's not like, you know, um it's not like you're you're having overlapping sub problems, right? It's like a pre-mpetition that you do, which is correct. Now, when you do a query on the prefix sum, do you do you find out every do you go to every index and find out its value or do you do prefix of R minus prefix of L minus one? you do prefix of R minus prefix of L minus one which is like saying that you're reusing like you're you're using all the answers that you've premputed and you're returning that right that is not dynamic programming similarly this is not dynamic programming here you're doing some premputation building a segment is like a premputation why do you need the segment to answer queries quickly that is exactly why you need a prefix sum to answer queries quickly but are you saying you are reusing some answers no You're not reusing some answers.
You are you are basically doing a clever premputation. So segment is a pre-mpetition, right? You're building the segment. It's like a pre-mpetition.
The update part that you're doing is like is making sure that the pre-ompetition that you've done gets updated in in login time. But it does not make it does not mean that it is not pre-ompetition and you're doing uh you know you're getting some answer and you're storing it and later using it.
It's not like that.
It's simply pre-ompetition.
Okay, does that make sense? So it's a bit abstract like you know if you want to call it dynamic programming you might as well call it dynamic program. Not not really that big of a difference.
Could you explain sweep line approach?
So sweep line is like a complex algorithm. It's it's not in the scope of level four or this lecture on segmentaries. Um if you want I can share some resources for you to learn about it but to be honest it's not very useful like in my entire CP career I have never used sweepline but I know how it works.
It is heavily used in lead code contests.
Um I I don't think so like if if there's a sweep line al sweepline concept it can be solved with some other algorithm.
This is what I feel. Sweep line is a very very complex algorithm by the way.
It is kind of difference arrays similar to difference arrays. Yes, I agree.
Okay. So yeah, I guess that is it guys for this class. Um please fill out this feedback form.
Okay. And yeah, I I'll also share the resource on sweep line for with you Kushal on discord.
Okay, thanks for attending and see you on witness day. We'll we'll look at problems on witness day and see how this segment can be modified to solve various different problems.
Okay. All right. Bye.
相关推荐
Re: 🗣️📍theprophedu📍2026 GST 103 CLASS (E-EXAM REVISION)
theprophedu
636 views•2026-06-04
WEB TECHNOLOGIES UNIT-2 | Degree 4th sem BCOM Computers web technologies unit-2 full explanation💯✅
LearnwithSahera
1K views•2026-05-29
More tests are always better? How to use AI to identify tests that bring little value
Alliance4Qualification
335 views•2026-05-29
Search Algorithms Explained in 60 Seconds! 🤖💨
samarthtuliofficial
218 views•2026-06-01
Making Minecraft Clone with C++ & Raylib
PecaCSLive
686 views•2026-06-04
People of Game of Thrones using JavaScript DOM
AltCampus
296 views•2026-05-30
Instagram accounts got PWNed
EricParker
13K views•2026-06-03
Introduction to Problem Solving Part - 1 | Lecture 1 | Intermediate DSA
ascensionix
107 views•2026-05-29
