A segment tree is a binary tree data structure that enables efficient range queries (finding sums, minimums, maximums, or other aggregate values) and point updates in O(log n) time complexity, making it superior to prefix sums for dynamic arrays where updates are frequent. The tree is built by recursively dividing ranges from the middle until reaching leaf nodes, with each internal node storing the result of a function (like addition, minimum, or maximum) applied to its children's values. This structure allows queries to be decomposed into at most 4 ranges, each requiring O(log n) time to process, while updates only need to modify O(log n) nodes along the path to the target leaf.
Install our extension to search inside any video instantly.
Segment Tree Tutorial for Beginners: Build, Update & QueryAdded:
So hey everyone this is Aush and in this video we will learn about segmentry. So segmentry is an range query data structure.
It is used for performing range queries quickly like uh to update an element within a particular range or to find the answer in a range L2R we use segmentry.
Before understanding the segmentry I have divided this video in four parts.
In first part we will learn what is the need of segmentry. In second part we will understand the working of segmentry. The third part is all about analyzing element space complexity of different different operations which we used to perform using in segmentry like uh doing queries range queries performing updates building a segmentry and in last we will implement it that is we will code it simply. Okay.
So let's first understand what is the need of segmentry because before understanding any concept what I think if we know the problem then understanding solution feels better.
Okay. So let's say I gave you this array and let me do zero base indexing and I ask you some queries of type L comma R I ask you to find the sum of elements in the range L to R. Now the most brute force way to do this is to iterate from L to R and add all elements in your sum variable.
For query 1 to 4, what you will do? You will simply iterate from index 1 to index 4 and add all these elements in your sum variable. 5 6 7 8 9 10 11 12 13. Similarly, for a query 2 to 5, we'll iterate our elements from index 2 to index 5 and the sum is 11 + 8 90.
Now the problem with this approach is let's say the size of array is n and if I give you two queries then in worst case your time complexity for each query will be n and your overall time complexity will be q * n okay for because for each query in worst case you over elements and for queries it will be q * n now to optimize this we have prefix sums what are prefix sums uh let me write this array 215 33 47 2 1 5 3 4 7 Okay.
Now uh we simply take prefix sum on this array where prefix of i gives you the sum of elements from index zero to index i.
So you can see for zero index uh prefix of 0 is two. For first index prefix of one is the sum of elements from zeroth index to that particular index here in this case it is 1. So it will be 2 + 1 3. For prefix of 2 it will be 2 + 1 + 5 which is 8 and so on. Okay. So these are prefix sums and using prefix sums you will answer each query in big of one because you just have to use this simple formula that let's say now I again ask you to find a sum in range 2 to 5 you cannot directly answer prefix of five um because prefix of five has the sum of elements from zerooth index to fifth index but I ask you the sum of elements from second index till fifth index. So in that case we need to subtract the contribution of these two elements.
Okay. And uh these two elements contribution need to remove. So usually we remove the contribution of elements till l minus 1. That's why our formula is prefix of r minus prefix of l minus one which you can see here prefix of 5 minus prefix of 2 - 1 1. Okay. This will simply give you the sum of elements in the range 2 to 5. Now again if I give you Q queries and each query now you will answer in big of one your overall time complexity will be Q one which is simply big of Q. Okay, now everything looks fine till here. But now I will add the main problem that let's say till here you was answering static queries. What are static queries? That the array was static. There were no updates on the array. The array was same from the start of all the queries until the end of all the queries. But let's say your queries are not static. Let's say I add updates in this queries that update the element at a particular index and then tell me the prefix sum in range L2R.
Now you cannot simply create prefix sum.
You can of course you can create you have to update the element. Let's say I ask you to update the element at fourth index. We have four update to eight. And now I ask you the sum of elements in two to five. Yeah. Now you can take prefix sums but for creating the prefix array you will need big of end time. Okay, this will be the time complexity of creating the prefix array. And for Q queries your time complexity will again become Q * N because now you have to update the element and again you have to take the prefix sum. So in this case your time complexity will become SK * N.
Now here segment helps us. We have to optimize this factor of n using a segment tree because segment tree can update the element in log of n time. We will see the proof of this ahead in video that how segment tree update the element in log of n time complexity and it and it also answers our query in log of n time.
So instead of n if we use n segmentry the time complexity will becomes q * log n.
Okay.
So this is the need of segmentry that whenever you have updates and you have to perform queries and for doing that your current time complexity is too expensive uh with respect to time with respect to uh constraints. Most of the times in uh on most of the coding platforms this q will be 10 ^ 5 and n will also be 10 ^ 5. I'm not saying always but in most of the cases and this will result into 10 ^ 10 which we all know uh which will not pass. We need something which is still 10 ^ 8 for 1 second time limit which is standard in competitive programming or DSM.
Okay.
And one thing I want to mention is that it is not like that whenever we have updates and queries together and we want to optimize our time complexity we will use segmentry because this here we were talking we were talking about addition and all functions won't behave like addition in case of some functions even if I don't uh give you updates and I just give queries like this that tell me this particular value in L2R still you have to use a segment and which functions are that maximum minimum let's say I ask you to tell me the maximum in the range 2 to 5 now in this case you need to iterate from 2 to 5 to find the minimum you cannot create a prefix minimum you can create a prefix minimum array but you cannot use this formula for that that uh we will uh take the minimum till fifth index and we will remove the minimum minimum from this index that is not possible because minimum, maximum, gcd this all are item potent functions whereas addition and zor are nonadmputent functions. Yeah, zor also behaves like addition in zor also you can use this formula but from foreimp important functions you cannot use this formula. Now what are item potent and nonadimpotent functions?
uh on internet you will see this equation about important functions that f of f ofx equals to f ofx. Now you want to get anything from this. It simply means that the value of your function won't change if you keep putting same type of input or same input in that.
Okay. For example, you can see here if we have a the max of a won't change if you keep putting the same input. Let's say max of a comma a will be a it doesn't matter how many times you give a as an input the value will always same.
Let's say with a you give b and its max is c. Now it doesn't matter how many times you give b as input its max will be always c. Okay. Similarly for minimum gcd. That's why this functions are said to be item important functions. Whereas addition is not like this functions. If you have a and you give a as an input, you will get two * a. Okay. If you again add an a, it will becomes three * a. Now here value is changing that's why addition is said to be a nonad important function.
Although it is not that important for understanding segmentry but I think let's mention this also uh we will need this concept in sparse table when I will be explaining sparse table at that time uh we will need this concept of adden potent and nonad potent functions okay fine I hope you guys understand you guys get what is the need of a segmentry now let's understand the working of a segmentry so I I have taken the same array and on this array I have already constructed a segment tree. I'm really uh sorry for this bad drawing. Actually I am using mouse. I don't have uh pen and that stuff for drawing this things. Uh this is the best which I can draw using the mouse. Okay. Sorry for this but I will give my best to understand uh make you guys understand. Now what is a segment? The formal definition of segmentry says segmentry is an binary data structure where your data is store leaf nodes and the intermediate nodes store the value of a particular function in the range which that node. For example, this node denotes range 2 to 3 and the value we have constructed this segment over addition function. Okay.
And the value of addition in this range 2 to 3 is 8. As you can see uh if you consider zero base indexing 0 1 2 3 5 + 3 8. This node stores 8. Now I know you guys will be confused like why this structure is like this? Why data is stored in leaf nodes? I will answer you each and every doubt. Just stay with me.
Now uh one doubt will came in your mind that why segment binary data structure?
Why not a normal tree an array tree? The reason is simple. The way segment tree is built and the way queries are processed inside a segment tree, its structure results in a binary tree. What is a binary tree? Binary is a type of tree where each node has at max two children.
Your node can have max uh zero it can keep zero children. It can have one children or it can have two children but not more than that. Okay. Now why binary? you will get once I will explain how a segment is built. Okay. And why data is stored in deep nodes. So let's first understand how a segment is built.
So um the length of our array is seven and the first index is zero and last index is six. Okay.
Okay. So let's understand how a segment is built in this array. The first index is zero and last index is six. So we will start with this range. Initially you start with the range. Okay.
Now forgot about this intermediate nodes this values. I will explain everything.
Now what you do? You simply divide your range from the middle. Okay. And the formula for that is pretty simple. L + R / 2. Using this you find the mid.
In this case, um will be 0 + 6 / 2, 3.
Okay, your is 3. And what you do, you divide your range in two parts. One part will be from L to mid that is 0 to 3. And second part is from mid + 1 to R that is 3 + 1 4 and R R is 6. Okay. L till uh mid + one and mid + one to R.
You divide your query like this. Now why we divide our query like this?
Everything I will explain while explaining you the times complexity.
Okay. uh no so don't keep on doubt like I know a lot of students uh instantly get out like why why from middle why not from any other point why you're breaking query like this everything has a reason behind that uh please stay with me and just uh try to understand what I'm explaining you will at by the end of video I promise you that your all doubts will get clear okay so once you divide your query from mid uh don't stop here again you have to keep your query dividing from the middle until your L and R doesn't get uh like it don't become equal okay because once they get uh becomes equal your middle will be always same for 1 your middle will be always one okay so we have to stop at that place so again you will divide your 0 + 3 divided by 2 it will be 1 so let me write here your mid will be two.
So we will again divide our range in two parts. One will be from L which was zero till mid which is 2 and another will be mid + 1 to R which is 2 + 1 3 oh sorry uh sorry my uh mid is not two in this case.
Mid is not two, mid is one. Uh 3x 2 is one. Sorry. Sorry. I'm really sorry for this. Okay. So 0a 1 and 1 + mid + 1 that is 1 + 1 2a 3. And similarly for this also that 4 + 6 / 2 that is 10 divided by 2 will be 5. So one column will be for 4a 5 and another will be for 5 + 1 6a r 6. Since c r was 6.
Now you can see here R L and R become same. You will stop here and what you will do you will insert the value at that index like 6, 6. At six index we have six. So we insert a six in leaf node. That's why leaf node contains the data. This is the reason why leaf node contains the data because at leaf nodes your L and R become same and we cannot further divide them. Due to that you we uh since we cannot divide them so our tree won't expand below it that's why we put the values at end okay now uh similarly for this you will divide it from middle uh 4 + 5 9 divided by 2 4 so l comma mid and mid + 1 r that is 4 + 1 5a 5 and similarly here this is 0a 0 1a 1 2a 2 3 comma 3 okay I'm really sorry for bad handwriting okay once your L and R becomes same just stop there and put that values put the values at that particular index from the array inside the node like at zero we were having two at one we have one okay at two we have five at three we have three at four we have four at five we we have seven and at six we have six. Now we will move uh from bottom to up since we will be on the leaf nodes. Now we will move from bottom to up. Okay. Now your uh recursive call of course we will uh you can build segmentry using iteration al iterative way also recursive way also but in this video I will be explaining the recursive way because it's easy to understand I think as compared to even iterative is also simple but for beginners I think recursive is easy as compared to iterative way now once your leaf nodes are filled you have to fill the values of intermediate nodes as you can See as you can see here we were having range 0 to 1 and from 0 to 1 we divide it from middle uh and it goes like 0a 0 and 1 comma 1. Now you have to combine their values. Whatever value is at zero. Whatever value is that one you have to combine them and you have to store in the node which is denoting the range 0a 1. Because here as you can see our range was 0a 0. At 0 we have two. At 1 comma 1 we have 1. But now I'm asking you the sum from 0 to 1.
So it will be the sum of 0 and 1a 1 2 + 1 3. That's why this intermediate node is storing three. Similarly here at second index 2a 2 we have five. At 3a 3 we have three. But from 2 to 3 we will have eight. That is the sum of its two childs. Okay.
Now again we will move back uh we will again come to 0a 3 because from 0a 3 we break the segment in 0a 1 and 2a 3. Now it's time to merge these segments again.
Are you getting what I'm saying? Earlier what we do? We break these segments. We break the 0a 3 segment in 0a and 2a 3.
But now we will combine these segments because we have the answer. Earlier we were not having any answer for a segment 0 to 1 and 2 to 3. But since now we have the answer so we will combine them plus 0a 1 2 3 will result in 0a 3. So 8 + 3 11 and you can see uh 3 uh 2 + 1 3 + 5 8 + 3 11. So this node stores the sum 11.
Similarly here 4a 6 we divide into 4a 5 and 6a 6. Now since both the ranges have the answer we will simply combine them in 4a 6. So 11 6 17 that's why I have written 17 here and you can see 4 + 7 11 11 + 6 17 okay similarly 0a 6 we divide into 0a 3 and 4a 6. Now it's time to again combine them because 0a 3 and 4 6 both have the answers. 0a 3 has answer 11. 4 6 have answer 17. We combine them and store 28. And you can clearly see that the sum from 0 to 6 for the complete array sum is 28 because 6 + 7 13 + 4 17 + 3 20 + 5 25 26 27 20.
Okay. So in this segment is built. This is the initial first part because before querying uh the segmentry we need to build a structure. So in this way the structure is built and I think now you guys will get the answer that why segment tree is a binary tree data structure because always we are dividing our query from middle okay not query I'm really sorry for the word query we are dividing our range from the middle once we divide our range from the middle we have two ranges one range goes on left side one range goes on right side uh sorry ignore this word left and right but we will be having only two ranges.
That's why a node has only two childs.
Okay. And it is same case for all other nodes also. On all nodes, we usually divide them from middle and we have we are left with two ranges.
So both the ranges acts as child nodes and once they get their answer, we combine their answer and stored in our current node. Okay. So this is why a segment is a binary data structure. I know still there will be one doubt that why we are dividing it from middle that I explain when I I will be explaining why the time complexity is log n okay so I hope you guys will be clear with the building part of an segmentry now let's understand how updates are performed okay since we are done with building a segmentry uh we have to solve the next problem for what we are learning the segment that how we will quickly perform the updates Now let's say I ask you to update the element at fifth index.
Change the seven to um change it to let's say four. Okay. Huh?
Change the seven to four.
Now you guys may have in your mind that now again we have to construct this uh complete data structure from scratch.
No, you don't have to construct this structure again from scratch like uh start from 0a 6 then divide it in two parts then divide this range in two parts this range in parts. No, if if you build it from scratch then there's no learning the segment because in perfect sums we were doing the same part that once an element changes we were uh building perfect sums again. But here you don't have to build this structure again from scratch. You just have to change the values at some nodes. How? I will be explain. Uh I will explain now.
Start with your range. Uh let me remove this.
Okay.
So start with your range 0A 6.
Okay. Why 0A 6? Because uh we will be start from root node.
segment is in root tree and we have if you have to traverse it you have to start from root node of course you can start from any node but still understand like see I'm not explaining this uh basic stuff like prefix sums and binary tree in that depth uh because if I keep explaining this things in detail then this video will become too much long okay this video will become too much long so keep it small and concise. I'm just uh telling this uh side concepts from an higher level. If you guys want to learn them, you can simply Google them or you can learn them from YouTube also.
Okay.
So we'll start from 0a 6 and our target index is five. We have to update the element at fifth index. We'll find the middle.
Uh I'm denoting middle from with m. So middle of 0a 6 is 0 + 6 / 2 3.
Okay. Now compare your target index to this middle element. Our target t is 5.
Is my five greater than three? Yes, five is greater than three. Now since your five is greater than three, tell me in which part you will move because left part has the r always has the range L to mid and the right part always has the range B + 1 to R and our target index T is greater than mid.
So of course the element which we have to update can't exist in left side because left side has only L2 mid. Okay.
But my target index is greater than this mid. It means we have to move in right part. So from this node we will go to this node that is mid + 1 r 4a 6. Okay.
Now we have 4a 6. Again find the middle 4a 6 divided by 2 10 to 5.
Now again compare is my target did my is uh like did my target exist in left range or right range. Okay if your target is greater than mid it means it is in right range. If it is uh equal to or less than mid it means it is in left range. Now since our target index is five and our mid is also five. So our target index exist in the range L to mid. And as we know in segment L2 m is on the left side of our current node. So from this node we will come to this node 4.
Once we are on 4a 5 again you have to repeat same process 4a 5. Find the middle your middle will be four.
Now again compare your target element with our mid. Since our mid is four in this case is my target element less than or equals to mid? No, we have two ranges. On left we have 4a 4. On right we have 5a 5. Is my target element in left range. For to have it in left range it must exist in the range L to mid. But no my target is greater than mid. It is five. It means it exists in right range. So from 11 we will go to this particular node. And as as you can see we reach our target node 5A 5. Here we have seven. Now we have to update this seven to four. Okay, I'm writing a four here. Now uh just don't uh exit from here. We have to update the corresponding nodes also because just think just think if this seven changes to four, which nodes will we have to change? This 11 has this five, we have to change this 11. This 17 has this five, we have to change this 17. This 28 has this five contribution.
We have to change this 28. Okay, that means we have to update this four nodes.
So that's why I said we don't need to construct the segment tree from the sketch again. We just have to change the values of some node because it's common sense.
These nodes has zero effect one uh because of change in fifth index because you can see they are denoting different ranges. Even this 4A 4 also has uh this 4A 4 also not contain the contribution of five but this ranges contains the contribution. So we need to update the nodes at that particular range. So once you update a four go back go back and again perform the same procedure which we perform in build. What we do in build? We merge the answers from our left and right shell. My left shell is four. Right shell is also four. So this 11 will becomes eight. Again go back combine the answer from your left node and right node. My left node is 8. My right node is six. So answer will not be 17. Now answer will be 14 for range 4 to 6. And you can see 6 + 4 + 4 8 + 6 14.
That's why 4a 6 is 14. and again at 28 combine the answer from left child and right child 14 + 11 which is 25.
Okay.
So in this way we perform updates over a segment tree. Now performing update is uh results in a log n time complexity.
Why? We will see ahead. So tell me is it not better than prefixum? In prefixum you have to update your complete array with an time complexity of big of n. But now you are just updating it with login time complexity. So it's far better as compared to prefix. Okay. So this is how updates are performed over segmentry. Uh it becomes too messy. Let me remove this to explain you guys the last part which is query. How we perform the query which is the most important part.
Okay. I hope you guys understand the update also. Now let's understand the query part.
how queries are performed.
We build the segment tree, we update the segment tree. But how we will answer the queries. Okay. Now let's again take the same query which we encounter in uh past examples that let's say I ask you to answer the sum of elements in a range 2 to 5.
So how you will find the answer for this particular range? Some of you may say that 2A 5 won't exist in segment. There is no way you can see 2A 5. Of course, there is no 2A 5.
But see how we will find the answer for 2A 5. Again, start from the root node.
At root node, you have 2 0a 6.
Find the middle. 0 + 6 divided by 2 3.
Now, we have two ranges 0a 3 and 4a 6. I hope you guys uh I hope you guys remember that formula that when we find mid we divide ranges into part L comma mid and mid + 1 comma r okay using this formula we get this two ranges now uh take any range let's uh first move to the left 0a 3 uh okay my bad I forgot to explain one thing that see when we you are in on a node. Uh at first we were on the root node. First compare is there overlap with your current range and this range.
If there is no overlap just get return from there. What is no overlap condition? Let's say this is your range 1 8 and this is our another range 9 11.
There's no overlapping between them. If I draw a number line, well, it's not necessary. I know it's very basic, but fine.
If you have a range from 3 to 6 and I have a range from 8 to 10, are they overlapping? No, there's no alarm.
Okay, fine. I will explain three types of overlaps out here. Actually we will encounter three types of overlaps while answering the queries. First there is a no overlap condition. When there is no overlap there is no meaning of going downward is in a segment because your query is something different and your range is giving something different answer. Your query is from 8 to 10 but your range is from 3 to six. So although if you go down you will divide this range from middle it will of course not contain the answer. So there's no point in going downwards. Just return from there. Okay. If there is an overlap, there may be two types of overlap still.
Either your both ranges may overlap partially. This is an partial overlap.
Or they may overlap completely. This is an complete overlap. Okay? And okay. So there's an complete overlap.
So I hope you understand this three types of overlapping using this we will find the answer for our query.
So when we were on root node 0a 6 check how your nodes uh how your answer query or your question query not answer query your question query is overlapping with your range. Now there's an complete overlap between this. Now just tell me one thing. This 0a 6 has the answer of elements in the range 0 to 6. Okay, we discussed this earlier in build part.
But we need the answer of the range 2 to 5. We need the answer in the range 2 to 5. Will it be good if I return this answer? No, because it has some extra answers. Uh I think our array is 0 1 2 3 4 5 6. Yeah, there are three extra indices. Uh where it is.
Okay, there are three extra indices 0 1 and six.
You don't need we need only answer for this range. So whenever you have this type of overlap what you have to do simply take your range uh which was 0a 6 divide it from middle using this formula la 1 m + 1a r and then process these two ranges. Now you are on 0a 3. Now again check again check how they are overlapping how they are overlapping. Now again in this case uh this is our current range and we need answer from 2 to 5. They're again partially overlapping. We cannot return this answer. Okay. So now again what you have to do you have to from middle and if you divide it from middle you will again get two ranges 0a 1 2a 3.
Now let's take the left one first 0a 1.
Now tell me one thing how these ranges are overlapping. There is no overlap.
There's not a single element which is overlapping. So what I explained or what I told earlier that if there's no overlap just return don't do anything just return from that because 0a 1 don't have a single element from 2 to 5 so just return from there okay you return a zero from here now uh let me explain here we are here 0a 1 yeah you return a zero from here now you are on 2a 3 just tell me how 2a 3 is overlapping with our current range 2a Right.
This is my 2 to 5 2 3 4.
Now, now observe carefully. We have 2 to 3. We have the answer from 2 to 3. Yes.
Now we have a complete overlap. We have an complete overlap. Now, in this case, we will return this answer. We written this answer. Now, we have answer for this part. But still, we need to find answer for this part. From 2a 3, we will get 8. From here, we get zero. So from 0 to 3 from this range we got 8 as a contribution in our question query.
Since our query is from 2 to 5 and you can observe 0 1 2 3 in 0 to 3 and my query is from 2 to 5.
How much this range is contributing in my query? Only these two elements 2 to 3 8 that's why we got a eight from here.
Now let's process the right part. We haven't processed the right part.
Uh 4A 6. Now tell me how it is overlapping with 2A 5. Of course there's a partial overlap. There's not a complete overlap. You will divide it from middle. Once you divide it from middle you have two ranges 4A 5 and 6A 6. Now tell me one thing. This 6A 6 and four uh 2A 5 has zero overlap. So we will return and zero from this set.
And 4a 5 has an complete overlap with our range 2 to 5. We have already find answer for this part. We just need for this part. And we get here 4a 5. Okay, it stores 11. So we will return this 11.
11 + 0 11. And we will again move upward and combine the answers from our left and right chain. 8 + 11 19.
So this is the sum of elements in 2 to 5. And you can verify. So 7 + 4 11 + 3 14 + 5 19.
So in this way queries are process in segment. Okay. Uh let's take one more example. Uh I think it may be unclear for some folks.
Let's take one more query so you guys will have more clear understanding for that.
Uh what happened to my undo?
Undo is not working.
Um just give me a second.
Okay, I think this is enough. Fine.
Let's remove this also.
Okay. Uh let's take another query. Uh earlier we take 2 to 5. Let's take 1 to 6.
Let's take 1 to 6. And again let's do the same procedure.
Start from the root node 0A 6 and we have 1a 6. Now check how these ranges are overlapping of although there is a complete overlap.
I know there's a complete overlap and as I said if there is a complete overlap just return the answer but who is overlapping completely with whom? Our question query is completely overlapping with the current range. But the current range has answer from 0 to 6. The current range has answer stored from 0 to 6. But we need to find the answer from 1 to 6. Okay. So we cannot return this answer directly. So what we will do? Simply break this from middle. If you divide it from middle we will get two ranges using the formula L comma mid and mid + 1 R that is 0 3 and 4 6. Okay let's process the right child first. Now tell me how 4a 6 is overlapping with our question query 1 6 and I think now we have a complete overlap. Okay we have an complete overlap. We want answer 1 2 3 4 5 6. We want answer for all the indices. And we got answer for 4a 6. For 4 5 6. So as we have the answer for 4a 6, we will simply return it. What is that? It is simply 17.
Okay. Uh don't return it immediately.
Let it store there. when we will uh arrive at this node after processing our left child. At that time we will combine the answer from left and right child.
Okay.
So we resolve this particular range. Now let's move with 0a 3. Now tell me how 0 3 is overlapping um with 1a 6. Of course there's an partial overlap or complete overlap but we don't want complete overlap. We want that our range must completely overlap with our question query. So we can directly return the answer. But here a question query is completely overlapping with our range.
So because our this range contains the answer from 0 to 3. But we want the answer for 1 to 3.
Okay. So what we will do? We will divide it from middle. Once you divide it from middle you will again get two ranges 0a 1 2a 3. Let's process the right range first. Now as you can see we need for we have the answer for 4 5 6 we want for the answer 2 3 we will be here in segment three since this is completely overlapping with our question query we will simply return this eight we will simply return this eight so this range has also been resolved now let's let's process this 0a 1 now this 0a 1 we just need answer for now one we have find answer for all dendas we need for one but 0A 1 has unsupport 0 and one but we need for one. So what we will do?
We will divide this 0a 1 from the middle and once you divide it from middle you will get two ranges 0 0 1.
Uh let's process the left range first with this. Once you go to 0 you can see our range is 1 to 6 question query.
Okay. But this range is 0. We have no overlap. So we will return zero from here. Now let's process the right range 1. Yes 1 comma 1 is completely overlapping with 1 comma 6 and even we were just left with this one and we want answer for this and what is the answer at first index it is one so this one will return from here now let's move forward combine the answers from both the child 0a 1 1 so this 0a 1 range will contribute only this one in your question query 1 to 6 and as you can see there we don't want this two we just only want one now this one and 8 will combine and will result into nine Okay. And that you can see also in range 0 to three in this range we just need these three elements from first index 5 6 7 8 9. And now we will combine this 9 and 17 together which will results into 26. So the answer for the range 1 to 6 is 26.
Okay. And since total sum is 28, we don't want this two. So if you remove two from 28 our sum becomes 26.
So in this way we get the answer of our queries using a segment tree or you can say simply in this way a segmentry works for answering our queries. Okay.
So now let's move to the next part which is understanding the time and space complexities of all the operations which we are performing. Okay. Okay. So now let's discuss the time complexities of all operations which we saw.
First start with the space complexity.
Now the space complex of the segment tree is big of n that is there will be always at max nodes.
Actually it's uh not n since in big notation as we know that we ignore the constant. So after ignoring the constants the space complexity comes out to be n where n is your array size.
Okay I will show you in brief that what is the exact number of nodes we are required to build a segmentry.
Now there are two scenarios of space complexity.
One is for the perfect pass of two and another is for non-perfect pass. Let's understand first for the perfect pass of two.
Why? The reason is simple.
Okay. And yeah, in this part also you'll get the answer why segment and we like is a binary data structure. Like as we saw the way we are dividing the queries, it results into binary. But why we are dividing the queries from middle? You will understand it in this time complexity part. Okay. Uh let's understand for space complexity.
As we guys as we everyone know that segment tree is an complete binary tree.
Okay.
Segment tree is a complete binary tree.
Sorry, sorry. Uh, sorry, sorry, please.
Sorry for my words. Segment tree is an binary tree. Segment tree is in binary tree.
Segment tree is a binary tree, not a complete binary tree. Now, what's an complete binary tree? A complete binary tree is that binary tree where all the nodes except the leaf nodes have two children. Let's see this.
This is an complete binary tree. Here if you ignore the leaf nodes, all other nodes have two children. The root node have two children. The intermediate node have two two children. Okay. Now for a complete binary tree there is a mathematical formula that if it has total nodes then the total number of nodes sorry if it has n leaf nodes then the total number of nodes are let's say leaf nodes are n dash 2 * n dash minus one and you can see here 4 2 8 - 1 7 we are seven nodes here 4 5 6 7 now why a complete binary tree uh has uh 2 * n dash minus one nodes where n dash are your number of leaf nodes. There's a proof for that also. It's a very simple mathematical proof. Just observe one thing at each level in a binary. These are the levels.
This is zero level or first level. This is second level. This is third level.
At each level you have some nodes. At first level you have one node. At second level you have two nodes. At third level you have four nodes and if you expand this let's say since we want a complete binary tree here at this level you have eight nodes.
Can you observe one pattern? The number of nodes at each level are the powers of two 1 to 4 8. So the total number of nodes are nothing but the summation of powers of two at each level. Uh that's why see uh ignore one base indexing we will do zero base indexing 0 1 2 and 3 this is 2 ^ 0 this is 2 ^ 1 this is 2 ^ 2 and this is 2 ^ 3 so 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 okay now tell me one thing this is in sequence this is an sequence of elements And this is not just a null sequence of elements. It's an geometric progression GP which we everyone have studied in our 11th or 12th standard GP.
Now if uh some of you don't remember what is an geometric progression, I will tell in short. uh geometric progression is an mathematical sequence or a sequence of uh numbers 1 2 4 8. This is our current geometric progression where your first term is denoted by a. Your common factor is d. Now what is this common factor? By multiplying this common factor, you get your next number in the sequence. For example, in this sequence, your common factor is two.
When you multiply 1 by two, you will get two. When you multiply this 2 by two, you will get four. When you multiply this 4 by two, you will get 8 and so on.
So d is your common factor. And let's say n are the total number of terms.
Okay.
Uh it okay. So there's a mathematical formula for the summation of geometric progression that summation of a geometric progression is a into d ^ n -1 divided by d minus1. This is the formula. Let's plug in the values.
S that is total number of nodes. My a is one in our current sequence.
these two.
Now here we don't know the like n so n - 1 / d is 2 1 okay we don't know the total total number of terms in our case total number of terms are nothing but levels because those many levels we have those many nodes we will have and we want a summation Let's solve this further. You will get 2 ^ n minus one.
Okay.
But you guys will say we have 2 ^ n dash minus one and we are getting something like 2 ^ n minus one how they related to each other. Now there's one more mathematical property for a complete binary tree. Now for this I don't have any proof and I don't think so it's it is necessary to give this proof that for a complete binary tree listen carefully for an complete binary tree total number of leaf nodes are always total number of nodes uh let's say n divided by two this is a mathematical property for complete binary um I don't have a proof you can search it over internet or you can simply draw complete binaries and you can observe that for any complete binary total number of nodes divid by two give you the leaf nodes number of leaf nodes okay now can we write this equation like this 2 * 2 ^ n -1 - 1 okay now what I said 2 ^ n -1 um okay 2 ^ n - 1 are your total number of nodes.
Okay.
Now just tell me one thing. If you multiply this L which is equals to N by2 L by2 are nothing but the total number of nodes.
Okay. Because nx2 this 22 will get cancel and we will get the total number of nodes. And more thing you can observe here if you multiply these two with this particular term you are getting your total number of nodes.
You are getting your total number of nodes. So aren't these two terms correlated to each other?
Can't I replace this 2 ^ n minus one with this nx2? Of course I can replace.
So once you replace that, you will get Oh, wait.
Um I think I messed up. Just give me a minute. Just give me a minute. I said something wrong. Just give me a minute.
Okay. Uh I'm really sorry. I'm really sorry for this thing.
I mentioned one thing wrong that total number of leaf nodes are not n by two they're n plus 1 by 2 in an complete binary tree.
Okay, in complete binary your total number of leaf nodes are n + 1 by 2 where n are the total number of nodes and you can verify this formula over here. Uh total number of nodes uh here 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 and deep nodes are 8. 8 + uh sorry total number of nodes 15 + 1 divided by 2 16 divided by 8. Okay fine. So this is the formula for number of leaf nodes. I don't have any proof I was saying. Now just tell me one thing.
We were here we wrote this equation like this.
Now tell me one thing when you multiply this term by two and subtract a one from it you get total number of nodes correct similarly if this term just multiply it by two and subtract a 1 what I'm saying n + 1 by 2 multiply this term by two if you multiply it by two 22 will get cancel and subtract a one this 1 one will get Answer you getting total number of nodes. You're getting total number of nodes. And to whom this term is equal?
It is equal to number of leaf nodes.
Okay. It is equal to number of leaf node. It means that in an complete binary tree total number of nodes are nothing but two times I denote it by L.
But above I mention leaf nodes with n dash is nothing but ndash minus one.
Okay. That's why in complete binary total number of nodes are 2 * n dash minus one where n dash are number of leaf nodes. I hope you guys get that uh we wrote a GP we wrote the summation of a GP formula we get this equation I wrote equation like this I remove a power of two uh earlier I was having uh n powers of two and if I remove one power I will be left with n minus one p of two okay and this minus one was there by a formula then I put an equation in front of you that in an complete binary tree the total number of nodes are nothing but n + 1 by2 okay n + 1 by 2 and what I said if I multiply this term by two and subtract a one from it I get total number of nodes similarly if we multiply this term by two and subtract one from it we get total number of nodes it means this term and this term are same so that's why I just replace it okay now the thing is uh so if your size of an array is complete power of two you will at max need 2 * n minus one nodes an easier size of array because in a segment tree number of leaf nodes are equals is equal are equal to the number of elements in an array that's why you will be using this number of nodes and in big of big notation we usually ignore this terms that's why we usually write it as big of n but some of you may caught me here and ask me okay Aish you told us for complete power of two but what about those paths uh let me check whether it is recording. Yeah. But what for those numbers which are not the power of two? Correct.
Correct. Uh we need a formula for them also. Now tell me one thing. Let's say I took n this n is not a power of two. Let's say a power less than that is 2 ^ k minus 1 and a power just greater than that is 2 ^ k.
Okay. is 2 ^ k. Now tell me one thing if I multiply this two 2 it will be equals to 2 ^ k. Similarly if I going to multiply this n by two it will be bigger than this 2 ^ k. This is basic maths.
Okay. So let's write this inequality that of course this 2 ^ k is greater than n. But if you multiply this n by two it will be greater than this part.
So let's write this equation like this that 2 ^ k is less than 2 * n.
Okay.
Now let's write this equation in a better way.
Let's assume for example in this uh two spar there are total n dash leaf nodes.
Okay. If you construct a segment tree for this size array, there will be n dash leaf nodes.
Now what you can do simply uh replace this 2 to the^ k with n dash.
We have ndash is less than 2 * n.
Multiply this n dash. Multiply on both sides by two. We cannot multiply on only one side of two. Since we have to maintain this equality, we need to again multiply here by two. Now subtract a one on this side. also subtract a one on this side. Now observe what we get. We get 2 * ndash minus one is less than 2 4 n -1.
Tell me one thing. We saw this equation earlier here. What is this equation denoting? It is denoting the total number of nodes in an segment tree for a complete power of two. So for this power of two we will have this many number of nodes and it is less than 4 * n minus one it is less than 4 * n minus one. Now from this tell me one thing.
If where um huh if for this size of an array we need this number of nodes then of course it's common sense that for this size of an array then definitely we're going to need less number of nodes. We need the number of nodes which are less than this value. Okay, let's say for that we need to tell capital M number of nodes. So the capital M will be always less than this term because it's common sense that for this size two of K let's say this is 8 this is 16 this 12 for 16 if I need this many number of nodes then for 12 which are less which is in less size of an array of course I will need less number of nodes for that okay and tell me one thing this 2 * n - 1 is less than 4 n minus - 1. We have derived this equation from here. 4 * n - 1. It means and this what what is this n? This n is nothing but here this n is the size of our current array. It means if I build a segmentry for this size, the total number of nodes I will be required will be always less than 4 n minus one. Okay, that's why see um this is an I know for some people it feels unintive but you have to accept the fact that for uh huh for a array size which is not a power of two you simply create an segment tree of four size remember this always and not for this you usually when we code no uh we Don't uh keep checking that the current size of an array is in power of two or not. We simply creates an array of this size. Okay, we simply creat this size. This is an upper bound.
This is an upper bound as you see here.
And as you as you know we usually ignore the constants in a bigger notation.
Hence the space complexity comes out to be big of n.
Okay, this video is a bit lengthy but I wish I should explain all the things which at least I know at my level because when I was learning segment I don't I was not aware with all this stuff I search over internet and learn this things and then I come to know that okay so that's why the space complexity is this from where this all so I wish you guys also know this So we are done with space complexity.
Now of course if space complexity is big of n time complexity of building a segment will also be big of n because you are building nodes. Let me go to the previous slide.
Since you are building n number of nodes and tell me um what work we are doing on each node.
You are going on each node dividing uh it in two ranges and putting two recursive calls. One call is going here, one call is going here and when they come back you are just combining their answer using an plus or minimum or maximum any function you can take. And these things happen in big of one. So on each node you are doing big of one. So for nodes n * big one simply n. That's why for building a segment tree you need big of n time 10 time again I will explain on each node you are doing big of one work you are not iterating over array or not doing something login or n work you're just dividing your segment in two parts and combining the answer on each node it is simply big of dividing like you are taking mid let's say one then you are putting two recursive call one plus um one for dividing from mid one for uh left recursive call one for right recursive to call one for combining their answer big of four which is simply big of n this is for one node and for all other nodes it will be big of n so that's why the buildtime complexity of an segment tree comes out to be big of n now let's understand this two point update and range query the most important thing like why we are using segment to optimize that prefix sums n factor to login using point update and range Now here again we need some basic school level mathematics.
Um let me erase this.
Okay. Now let's discuss the complexity of point updates. As we saw in the previous slide and previous part, how we were updating.
Okay, how we were updating? We were finding the mid we're comparing it with our target element. It's completely messed up. Okay, we were comparing it to target element and we were trying to reach to the leaf node to update that element. Now it can be any path. It can be this path. It can be this path. It can be any path.
Okay.
I wish my undo operation work.
That's not working. It's not working.
Okay. Leave it. Leave it.
Now it's time complexity is log n where n are the number of nodes in a segment.
How? Tell me one thing. Uh as you guys learn in school what log b to the base a denotes? This denotes how many powers of a are required to reach b. Correct? This denotes how many powers of a are required to reach b. Tell me one thing.
What log of n to the base 2 will denote?
How many powers of two are required to reach n? How many powers of two are required to reach n?
Okay. So huh.
Now tell me what this denotes 16.
As we know uh 2 ^ 4 is 16. It means we need four powers of two to reach 16. We need four powers of two to reach 16.
Can I say it like this? Uh how many powers of two you are required to convert this 16 into one or how many times you need to divide this 16 by two get one. Of course you need to divide it four times because using four powers of two you have constructed this 16. So you have to remove all the four parts. So it means you have to divide it four times to reach one. It means these two statements are interchangeable. That for any number n how many times we need to divide it by two to reach 1 is nothing but log n to the base 2. Okay.
Now I know uh again someone will ask I wish this was a complete power of two.
What for the other uh like I have seen that log 2 10 is something I think 3 um log 2 10 3.3 something okay this is 3.3 something so it means we need 3.3 operations now we usually take ceiling value of this you Take ceiling value or we write a + one that approximately four operations are required.
But now someone will say see this 10x 2 you get a five by 2 you get a two 2x two you get a 1. So 10 to the one operation two operation three operation. Yeah of course we need three operation but not in every case. I will explain.
uh keep this aside for a time and keep this in mind. Now similarly tell me one thing for any range L2R how many times you can divide it by two so that it remain divisible. No remain divisible in the sense how many times you can divide a range until and unless L and R are not equal. Till that you can divide them. Once they got equal you cannot divide them further. So how many times we can divide a range L to R? Of course it is R - L + 1 log of 2 R - L + 1. Uh let's say your query is from 0 to n minus 1 that is for your complete array and I'm considering this equal this term equals to n. That's why your buildtime complexity comes out to be log n to the base 2. I know it's still confusing for some of the people.
See for those who are still confused with it tell me one thing what we are doing while we are updating an element.
We are taking L and R. We are dividing them by two. Then we are left with two ranges L comma M + 1 R. Based on our target element, we choose to with which with which with which range we need to continue either with L comma M or either with M + 1 comma R on that basis we are choosing with which we want to continue on the basis of T. Again let's say we decide to continue with this we divide we find divide it from mid like see now see we are having L comm dividing it from middle if your target element is somewhere here you are proceeding with this part again you have L2 M you're dividing it by two since your target element is here and you are proceeding with this part um it's too big this part your target element is here again you are dividing it from middle since Since your target element is on left side, you are proceeding with this part.
Okay. Again you divide it from middle.
Since your target element is on right side, you reach here and you reach on your target element. Now what you are doing? What you are doing? You are continuously dividing your range with by middle. You're dividing it by two. And till what? You can divide it by two.
Till what? You can divide it by two until it is not equals to one. Now you guys may say I wish that you we our range is becoming L or something K, K.
It's not becoming one. I know it's not becoming one but both have same meaning.
Both have completely same meaning. Um to explain that see I will take 1a 10 divide it from middle you will get 1a 5 6a 10 divide this again from middle you will get 1a 2 3a 5 divide it from middle 6a 10 + 6 16 divided by 2 8 and 9a 10 okay now again divide these ranges from middle. If you divide this from middle, you will get 1a 1, 2a 2, 3a 4, 5a 5, 6a 7, 8a, 9a 9, um 10a, 10.
And you have to divide these ranges further more for 3, 4, 4 and similarly for them. Now how many levels required?
We were having 1a 10. Then these two this this total we divide these ranges four times.
Four times.
Okay. Technically most of the ranges ended at third time. But for some we need to divide them four times.
Similarly for 10 as explained you did by two you will get an five divided by two you will get an two. You divide it by two you will get an one. You divide it three times. But as I told earlier for nonpars of two you have to take the ceiling value which will comes out to be four and you can see here we divide this range at max four times you cannot divide it more than four times. Okay, that's why for numbers like 10 which are not the power of two we consider this formula or you can say this and for normal powers of two you can simply write log n to the base 2.
Um this seems confusing when you will listen first time.
uh what I say uh like um what I wish just uh rewind back the video and watch again I 100% assure that you will understand it first time even I was confused with this but when you will see this two three times you will definitely understand what is happening okay all is uh all from basics that what this equation denotes what is the meaning of this equation or how many times uh we can divide divide a number by two reach one. Similar analogy we use for a range. How many times a range we can divide by two so that it we can divide it or it won't become close to one. Then we did a dry run on a range 1 to 10 to show you guys that although it don't reach one but reaching this terms is equally similar to reaching one.
This reaching from 10 to 1 is similar reaching 10 to this terms. Okay, that's why we need same number of steps. Now in 10 also you want to require four steps.
Like if you divide it like this by taking ceiling value 10x 2 5x2 is 2.5 ceiling value is 3 3x2 is 1.5 ceiling value is 2 2x 2 1 1 2 3 4 Now you need four steps I hope you guys understand this part.
Now let's understand the last part of range query. This is the most difficult part for me to explain just because to explain this part I don't have any mathematical proof even I read lot of blogs on internet for the proof of that but I didn't find any blog which explains that why range query is login but uh when I was running a segment tree Um so at that time my tutor taught me how this comes login using an observation. Yeah.
So now I'm drawing some stuff to show you guys how this comes out to be login.
Actually it's not login. More precisely it's 4 * log of 10.
Okay.
In worst case it goes this. But in big notation we don't ignore this constants. Sorry we ignore this constants that's why we write login. Now I first tell me one thing ignore this four actually I need to give you proof for this four that is the hard thing explain this but it's pretty simple it's very easy because as you guys see did you guys observe one thing that the height of your segmentry will always be log of n to the base 2 because as I told earlier for any number how many times you can divide it by two you can divide this many times so for range 0 to 6 or so not 0 to 6 I'm still in that example 0 to n how many times this uh uh range can be divided by two of course this range is divisible only this many times at on when we are dividing it we are adding an extra node in bottom direction we are increasing our segment three side by one. So if you are like uh if you are dividing your number this many times it means you are adding this many terms in this many nodes in your segmentry in bottom direction it means that is the height of your segmentry.
Okay. What is height? Height is nothing but maximum distance which you can travel from a root node to leaf node. In this case, height is three. 1 2 3. Okay.
Maximum distance not distance maximum distance because here distance is two from root to leaf. But we consider maximum distance as the height of your tree.
So if this is your height and as we saw in u query part that tell me one thing how deep you will go in worst case you will go to leaf node to find your answer. You will go to leaf node and what is the depth of each leaf node? The depth of each leaf node is log n to the base 2.
Okay. So it means the time complexity of quering is simply login because in worst case you will go login times down and tell me one thing in each query what you are doing you are just adding your ranges you're just performing addition and it's a constant time operation so on each node you are performing addition and you will travel login nodes like to be precise two times login because 1 2 3 and again you will go backward but since we ignore constants and on each node since you are doing constant time of work that's why your time complexity comes out to be n * login okay but I will not leave you guys here the thing is the thing is if you guys observe we are not dealing with only one range like see Here if you have 1 comma 8 you have 1a 4 5a 8 what I tell earlier for one range it is login but at one we are dealing with lot of ranges at lot not lot of ranges but we are dealing with pretty much ranges at a time 1a 4 you will divide it from middle 1a 2 3a 4 5a 6 7a 8 for one range I tell log of n some of you will ask what about other ranges now what I'm saying combining for all ranges the time complexity in worst case comes out to be four times login now you guys will say why four only the range can be divided anytimes let's say you take 1 by 100 there will be lot of smaller ranges at bottom why four * log 100 to the base 2 for Let me draw something for you so you guys will understand.
Okay. Um Okay.
Actually I learned this uh thing from Priyan.
If you are doing computer programming of course you know who is him.
Okay, this is my range. Let's say 1 till um 10. Let's consider 10. 1 5 6 10 1 2 3 5 6 8 9 10 and I'm not numbering at bottom.
Now see what I'm saying any range you are processing in a segment tree will get break at max four times. It won't get break more than four times. It will only get break four times.
The reason is very simple. Just observe what I'm doing here and tell me one thing. Okay.
Let's say your array size is 10 and we have a pretty large query. This is let's say this is your query range. Okay.
And sorry for this and let's say this is your query range.
What you will do? You will simply divide from middle. You know how we process queries in a segment. We divide them from middle. Once you divide them from middle just see what is happening.
This part acts as a suffix and this part acts as a prefix. If you are getting confused with these prefix suffix terms, ignore them. But then we have this part and part. Okay, we have this part and this part.
Now just tell me one thing carefully. We have to process now this range and we have to process this range.
Still they are partially overlapping 1 to5 store the answer for 1 to 5. But we want for something let's say 2 to 5 answer. Okay. So we cannot return the answer from this node directly. So what you will do simply you will divide it from middle. When you will divide it from middle can you observe one thing at bottom you will be processing this particular range.
at bottom at bottom. You will be processing this range and this range one from here to here.
And you can clearly see that this part was already completely overlapping with this part with this part. But we were with this segment at that moment. So we were not able to answer directly. But once this segment becomes separate from us, we were left with this part. It was completely overlapping.
But we cannot uh return its answer directly from here. So you return its answer from here. And for this segment you will again process similarly from here that you will divide from middle again you will be left with two segments and those two segments you will left with four segments but out of that four similarly here also this segment and this segment will not further get divided because they were already overlapping completely.
Um let me explain again. Let me explain again. Let me explain again this thing.
Let me remove this numbers also. Forgot about this numbers and just focus on this diagram. Just focus on this diagram.
Let's say this was the query our range query. Okay. Now since this is not uh we written the answer directly from this level, we will divide it from n. Now you will be left with this two ranges once you divide it from middle. Now what I'm saying once you divide this uh range into this in two further it won't get divided as I told earlier we have four times login a range will get divided at max into four ranges further that it will never get divided the reason you can simply observe now from here just observe carefully just observe carefully what we have did here we have divide this range in two parts this is our array range here this is our query range this is our array range We have divided from middle in these two parts and now we have this our query range.
What we will do? We will divide it from its middle.
Now although the medals you can see okay wait I'm sorry I'm really sorry. Uh while processing queries we usually don't divide our range uh query range by two.
We divide arrays range by two. I'm really for I'm really sorry for this.
So we divide our array range into two parts. Now tell me one thing. The right part is already overlapping with our query. But this left part is not overlapping. That's why we will again this divide this range in two parts.
Array range. Once you divide it in two parts tell me one thing. One this part will completely overlap with our query range. As I explain here uh how query works in a segment. Whenever there is a complete overlap, we returns the answer.
Let's say you are 2 3 your range question queries from 1 to 10 and your 2 3 2 3 is completely overlapping with your question query and it's contributing it in it. So we return answer directly. Similarly here as you can see this question query was not completely overlapping this AIC range was not completely overlapping with a question query. That's why we divide it from middle in this two parts. But you can see the if you see the part from its middle it was already completely overlapping with our question query.
So that's why whenever you divide your query array range in two parts not query the right part always completely overlap with your uh query and you simply return that here also same thing will happen that okay let's say ignore this here same thing will happen although your array range is not completely overlapping with a question query But just observe the part from middle it is completely overlapping. That's why when you divide our arrange from middle this part completely overlaps with it and you return the answer for it and this part still won't completely overlap.
Okay. So we proceed them similarly as we proceed this range again it will get divided into two ranges. Again they will divide get divided into four ranges.
them will directly return the answer and again these two will process. So in this way a query can at max uh get divided into four different queries. That's why it is said that the time complexity for range query is set to be four times login. Okay.
Um still one last time I'm explaining this third time I'm explaining this. I know it's way confusing to understand last time I'm explaining one more last time.
Let's say you have this your range why it's not undoing.
Okay, notice how this is your array range and this is your query range.
Array array query range is from this to this. Your array range is not completely overlapping with your query range. Hence you divide your uh array range from middle.
Okay.
Your query is still like this h your query is still like this. You divide your array range from. Okay. Now again as you can see your ar range is still partially or not completely overlapping with your query range. Again you divide your ar range in two parts.
Now observe one thing.
This is the middle of your ar range.
Can't you see the right part of the middle is completely overlapping with your query range. Yes it was overlapping. That's why when you divide it in two parts just one part is solved forward. This part's answer is written in big of enter. Similarly for here when you divide this in middle the left part was already quickly overlapping with our query.
Our arrange is left range from the middle already overlapping completely with our query range. Hence for the left part we return the answer but for the right part we process it.
So as you see our array range or we at max go till four ranges but when we are with four ranges two of them always get cancelled and we only process two of them ahead.
Okay. So again this two will break into two and this will create four.
Again this will get cancel and we process this two only till bottom. And as we know it is login at max we are can process four queries at a time that's why the time complex is set to be four times login. As you guys observe that a range cannot get break more than four times. So at max we will process only four ranges.
Okay. But in big notation we ignore constant. That's why the range query time complexity is log n. That's it.
So this is all about the analysis of time and space complexity. Now let's move to the last part of this video. I Okay.
So now we will be coding a segment tree and after that we will be solving questions. I have decided to uh solve the questions from CSS. We will be solving most of the questions from CSS range query section. Even I will teach the sparse table and finick. So now for coding purpose I will be using Java.
Although I have done computer programming from last 3 years in C++.
I has always used C++ for CPDSA but the reason I'm I will be coding in Java is that most of the CP resources or DSA resources are available in C++ according to me at least I observe that most of the resources are in C++ even most of the my friends who used to code in Java struggles like at one level language doesn't matter if you're logic develop language doesn't matter in language you are coding but still most of the in C++ so that's why I think if we put some resources from my site it will be in Java but still in uh description you guys will get C++ code for this okay okay so let's move to the last part which is implementation now we will simply implement all the concepts which we have seen till now in the code And before starting to uh starting before implementing it I would like to mention one thing that I didn't tell you that why we are dividing query from middle as I told you like I show you why the segment structure comes out to be a binary tree data structure okay but I didn't tell you why we are dividing the queries from the middle its answer is pretty simple Why we are using segmentry? Let me say whether it is recording or it is recording. Why we are using segment?
We are using segment to optimize our queries to optimize our updates. Okay, we are using it to reduce the time complexity.
Now the thing is to optimize the time complexity.
Okay, if you have an range when you divide it from middle lum as I show you mathematically we can uh divide it in at max this steps. Okay, we can divide it in at max this steps because of only this reason we process the uh queries in segment like this that we divide them from middle and because of that it structure comes out to be a binary data binary like a binary.
This is the reason why we process queries like this because now tomorrow someone going to ask someone going to ask me that what if I divide it from here. Yeah, you can do it. Uh you will be left with something L comma K and K + 1 comma R.
Okay.
But now this will not results in log of length comma two time complexity overall. It will be greater than that because we are not dividing from middle we are dividing from ends. And this length are variable now. But earlier when we were dividing from middle we were getting uh let's say length is n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n nx 2 n by two parts again we divide them we get nx4 nx4 and as we keep dividing we reach one at some moment and what is how many steps required this much. So because of this reason and then segmenting oh okay so because of this reason and segmenting we divide queries from and because of that it structure comes out to be like an binary tree and in case of complete pass up to complete binary okay now uh let's say we have this array 1 84 10 and I have to construct a segment tree over it how we going to construct this in code. Now if some of you have idea of a binary tree and you have implemented it, you guys have deal with uh objects in C++ pointers.
Okay, like you will create an class or like node in that you have some parameters.
Then in C++ you put pointers like this not like this but just telling you put pointers. So a lot of people will ask are we going to implement this things in segment? No we will not implement segmentry like this. Okay we will construct a segment or a raw array. The reason is very simple.
Whatever numerical functions you are dealing with whether it may be an addition, subtraction, division, multiplication, GCD whatever it may be their results are numeric it's integer long whatever it may be it's a numeric value and you can simply store it in an array you can simply store it inside an array but there is need to create all those me but it's not mandatory that like It's not we always create an segment tree or and draw array. We will be always able to create an segment tree or an array.
Sometimes it may happen that you need to create an class uh inside that you have to uh create uh like huh you need to create a class with some three four parameters and instead of numeric value in that array instead of integer array you have to create the array of those objects because in some questions we have to deal with some more stuff okay we will see those questions ahead uh while solving questions from CSCS This just uh telling that it's not necessary you will always implement a segment and raw array. It may happen that we need to create a class and we have to store the data inside its object and that object we have to store in this array. But at the end you want to store every all the nodes inside an array.
Now uh just ignore this uh formula. It's in simple formula and focus here.
Huh? I'll focus here what I'm telling consider root node at first index. We will store the root node at the first index.
For left node, we will take a value just greater than that. Uh and for one, it's just next number is two. For it right, we will take a value greater than its left child number. For two, the value which is just greater than that is three. Okay. Now again move to the leftmost child. We are uh like we are moving level by level. First this level, then this level, then this level. We assign this no root node as one, left child as two, right child as three. Then again move to the next level. Once this level is over, move to the next level.
I'll start from the left side. 2 3 4 5 6 7.
As you can see, I have assigned numbers to each. Why I assign these numbers?
Because we should know at which index we have stored the value of this node. Root node at first index, leftmost child second, rightmost child at third. Then for the next level, leftmost child at fourth, the next child at fifth, the next child at sixth and the last one at seventh. And not for just this for every segment from now, you will store nodes in this version. Now uh like a lot of people's implement an segment tree in an zerobased indexing also but I have a habit from past 2 years to implement a segmentry over an one based array. Okay.
So there is no any issue just uh in you have to like instead of 4 * n minus one you have to create an array of size 4 * n that's it no no difference and even in implementation you won't face any issues just there will be change in formula I will show that how you will change this formulas for zerobased indexing okay now you guys understand how we going to number the stores 1 2 3 4 5 6 7 if There are further nodes like this 7 8 9 10 11 12 13 14 15. So in this uh manner we're going to number the nodes of our segment tree always. Now once you number the nodes how we will uh put this values inside an array in code. It's pretty simple. Now focus on these two formulas for left child. If you start we will start with node one while doing transition if your value is equals to node for left child you will multiply it by two and for right shell on multiplying it by two you will just add one inside it let's understand this thing by doing and dry run we start with the value one okay uh let's do the indexing of our array 0 1 2 3 0 to 3 we have the range now we are building a segmented Remember what steps we follow while building a segment tree.
We took the range. We take the range and divide it from middle. If you divide it from middle, you'll be left with two ranges which is nothing but 0a 1 and 2a 3.
Okay.
Now from the root node you are moving to this two.
Sorry.
Huh. Now from the root node you are moving to this two nodes. Okay. And here we have our node value equals to one.
Currently we don't have value in our left and right child. So we will store nothing here. Once they have their values we're going to merge them and store here. Okay.
So what I'm saying for your left child which is this 0a 1 just multiply the value of your node by two. It's one multiply it by two it will becomes two.
Okay. So it will come at two and for the right child multiply it by two and add in one. So 1 into 2 + 1 is three. Okay.
So for this we have three. That's why I said 1 2 3. For this one for this two and for this we have here three. Now uh let's say you are in this range 0a 1 and the value of node here is two. Now again divided from middle you'll be left with 0a 0 and 1 comma 1. Now again use the same formula for left child multiply your value of node by 2 2's are 4 and for right child it will be 2 * node + 1 2 2's are 4 + 1 5 okay as you can see 4 5 now let's process this range 2a 3 um divide it from middle you'll be left with 2a 2 and 3a 3 here the value of a node is three multiply the value of your node put by two for left check 3 to the 6 as you can see here six for this left and for the right one multiply it by two and add 1 3 to the 6 + 1 7 so you can see we have seven okay so I hope you guys understand why we have this formulas because using these formulas we have this sequencing which I show you to store the elements Okay.
Uh for zerobased indexing I will explain in code. Now let's complete our dry run.
We are on 3. The value there is 10. So I will insert a 10 at seventh index. Okay.
Then my recursive call will come back from here to here. Let's say first is goes on right child. Now it goes on left child.
And here L and R will becomes equal. So we have sixth index for this. We will insert here the value four. Okay. I insert here the value four.
As as you can see I insert four 10 at six and seven index. And now my recursive call will come back. And as now as of now we have the answer in our left and right child. We have to combine them to find the answer for our current range. Here this node is denoting the range 2 to 3. So it it will just combine the answer from 2 * node that is left child and 2 * node + 1 that is right child 6 + 7 um 14 sorry 4 + 10 14 okay 4 + 10 14 and what is the index of this node for this it was 1 and this is a right since 2 * 1 + 3 so here we will store 14 simply okay Now um let's process this ranges. Let's say we are in right l and r are equal. So it's time to store the value in the leaf node that is uh this is the index which we have calculated in the array using this formula. For one we have 8 and its index is five. So here we will store eight. Okay.
Then from here our recursive call will come back. Again we will put one recursive call over here. And here as you can see we have 0, 0. L and R again become same. And the index we calculated for it inside an segment array is four.
So at fourth index we're going to store the value one.
Once you store the one your value uh recursive call will come back. And since left and right child has their values calculated you have to combine them. So left child it is eight, right child is nine. Fourth and fifth index. We have to combine the values of fourth and fifth index. 8 + 1 9 you have to store here 9.
Now this recursive call will come back to the root node. And this recursive call will also come back to its root node. Since for now root node uh its left and right child have the values already calculated. We will store them at the index to which root node is pointing. So for root node we start from the first index. So we will store at first index and the value is nothing but uh index 1 for left child 1 * 2 2 9 1 * 2 + 1 3 for the right child 9 + 4 13 20 um 8 + 1 9 sorry 14 + 9 23 9 + 4 14 + 9 23 okay as you can see 23.
So in this way we store the values of our segment tree inside an array using this simple formulas and simple numbering as you see 1 2 3 4 5 6 7 now for update also as you guys know if you have to update uh the value at let's say this particular index second index it's four and let's say I have to update it to 97 you know the update logic which we which we used in the previous part that divide your range from middle. Check it with the target index. If it is less than equals to middle, go to the left child. If it is greater than middle, go to the right child. Once you reach to the leaf node, you have to update this four to 97. Okay? Whose uh index will be six. And then just you have to combine the answers. This uh 97 6 and 7 index uh 97 and 10 will result in 107. And the index for this node is three. So here you going to instead of 14 you going to store 103 in an array. Now again uh since you this node was contributing answer in this node. So we change the value of this node. Even this node was contributing the answer in this node. So we have to change the value for this node also. So we have to combine the answer from the left node and right node. For the left node it won't change.
It is 9. For left node formula is 2 * node that is 2 * 1 it is 2. It is 9. And for right node it is 2 * 1. 2 * 4 + 1 2 * 1 2 + 1 3 107 107 + this 9 116 instead of 23 you will store here 116. Okay.
And for query also it is exactly similar. Okay. It is exactly similar.
The values you will return using simply if your array name is sect ti sect tree of node this will be the value which you will be returning while query because sector tree is the array this array if you name se and node is the index so of course at that index the value will be stored up so you have to just return it things will things will be more clear once we start coding it so I think let's move to the core part I will be using Java for coding but for C++ users I will put my GitHub repo in description where you can find both Java and C++ code. Okay.
So let's implement this code or this logic.
So I will create a class segment.
Now uh even in C++es you can simply create an global I like this. Then you can implement three functions build query update.
Okay there is no need to uh create a class always but for uh being a better practice I am creating a class. Okay. So we need first the size of our array which will be n public int n public uh we need our secretary array which will be of type integer I will name it segdt in short form now let's create a constructor public sector integer this dot = to okay uh even let's create the object of our array ht= to new in as I told we will create the array of size 4 * n even I have proved this why it's four * n okay so by default in Java all the values will get initialized to zero in C++ vector and its constructor Right.
Now let's write the build function. The code is pretty easy. Code is damn easy.
There's nothing hard in the code. I don't know why people uh says that uh segment segment tree has really long code. It's pretty hard. This is that but it code is damn easy.
Let's first implement the build function public void build.
Now here we will be needing three parameters.
ln R which will denote the range for our current node and of course the index of our array that is node as I saw here sorry as I show you this node which will start from one. Okay. Now what we will do simply for building we usually calculate the M integer need equals to L + R left by 1. Um okay let's write it in simple way l + r / 2 once you calculate the mid we will put two recursive calls um let's say let me undo this thing okay okay good currently we are at 0a 3 uh we will calculate the mid and put two recursive calls one for the left child, one for the right child. For the left child, you will do two times node. And for the right child, you will do two * node + 1 to get the indexing 2 and three rhythm. So simply we'll put a recursive call L comma mid, 2 * the left child. And for the right child, mid + 1, R comma 2 * 1.
Okay.
Once uh your both recursive calls came back after doing their work, you have to combine their answers to calculate the answer for your current node. So for that we will write a merge function and we will pass node in that public world merge node.
So node is denoting our current sector.
It will combine the answers from left and right side which will be 2 * node and 2 * node + 1. So it will be hgt of 2 * node plus of 2 * node + 1.
Okay.
But what will be the base case? As we know when L and R becomes equal like 0 comma 0 when L and R becomes equal you have to stop there because you reach a leaf node and you insert the value from your array on that leaf node.
So we will write the base case if l= to= to r set tree of n equals to okay we forgot to pass or accept our array array of l. Why array of l because your l and r becomes equal 0 and 0 is denoting the element which going to store. Okay. Then return.
Ah. Okay. We need to pass array over here.
Over here.
Okay. So this is a build function.
Um should we test it or let's complete the rest of the functions?
Let's test it. So I will create a class public class name public static body name.
Okay. So let's take the same array 184 integer = to 1 8 10.
Okay. So integer equals 24 let's create the object of our segment tree equals to new segment tree and inside that we will pass the size of our array and once object is built we will build a tree.
Now we have to pass L and R. So my L is 0 over here.
R is n minus one that is three because 0 1 2 3. Okay. Our node will be 1. We will start with as I told earlier we will be doing one based indexing over se array and let's pass our array. That's it.
Okay.
So let's print the values. Um this print over here must be less than since it's a power of code there will be for it's seven nodes so less than equals to 7 + i s out s out s Okay, fine. Now, let's run this code.
Oh, sorry. Print len.
As you guys can see, we have the exact array which we built. Oh Wait, wait, wait, wait. Let me redo it.
Uh, redo is not available. Okay, okay, no problem. Um, let's add it quickly. So, for here 1 2 4 at four, we will insert one.
At five, we will insert eight. At six, we will insert four. At seven we will insert 10. This node index is three which will combine 6 and 7 that is 14.
For this index is two it will combine four and five that is nothing but 8 + 1 9. And for root 2 it will be 14 + 9 23.
So as you can see 23 9 14 1 8 4 10 2 9 14 1 8 4 10. So our build function is working correctly.
Now let's write the update function.
public void update integer l our array range and move into the target index and the value which we need to put over there.
Okay. So in middle also what we do we calculate the mid sorry in upidate also what we do we usually calculate the mid and what I said earlier we will compare our target index with mid if my target index is less than equals to mid we will simply put a recursive call for the left child okay let's say our target index is one you calculate the mid for 0 to 3 it comes out to be two Okay. And your one is less than equals to mid. So it means you have to go in this direction because as you know one is here.
So update L comma R comma 2 * mid comma target index comma value. Okay.
else.
Oh, spelling mistake.
Let's copy the same line over here.
2 * m + one for the right chain.
And here it will be mid for and here it will be r. Okay. M + one.
Okay. And at last after since as I told if you update this node this node is contributing in this node and in this node. So for both of them you need to call the merge function to merge the values from left and right. So you will call the merge function over here and you will pass and the base case will be simple as you know if L and I become simple we reach our target index. So SGT of not don't write here target index. Okay, the target index is with respect to array in SGT. For that particular node, we will have a particular index in our SGT array which in this case is equal to node equals to that value. Okay. And let's return from um let's check whether it is working fine or not. HD.
Not upper date it's update. Okay. So 0a 3 comma 1. Let's say uh let's update this 8 to 7. So in that case here we will be having 7. 7 + 1 here we will have 8 and this will be 22.
So my target index is 1 and the value I want to put is seven.
And let's paste it here.
And I just want to print uh HGT dot HGT.
Okay.
What's wrong?
Why the values didn't get updated? I think I messed up somewhere.
here zero. It shouldn't be equals to zero. We should have something like 22 uh 22 84 10.
This was my target index.
I build this inventory over here. Okay.
So, this is the mistake.
Fine. Uh this thing is not correct but my value didn't get update.
Why this is happening? So let's debug this code. Uh L= to R sdgt of node equals to my value and I just return from there. I calculate the mid.
I compare my target index with mid.
So L mid 2 * not it's two times more.
So this is the way should you should also debug your code. Just find the problem as we saw the problem was with update function because build function was working correctly.
So just check that particular code below a lot of people ask me how you guys debug your code in contest or during ICPC in such pressure situations. So whenever you encounter a bug or some weird result just debug line by line.
Now here I was uh we have already tested a build function but if we didn't test it uh I would first print the values after doing a build. If everything seems fine then there's a problem in update function.
So simply I going to check the code line by line. If code seems correct for me then I will put t print lines at each uh position like uh here here after merging to check uh how values are behaving. In this way we usually debug our code. So my update function is working correctly.
Now let's write the last function public int written type as again because we need to return the answer same ind r integer capital l and capital r will be our query range. Okay this will be our array range and this will be our query range. Now again find number R / 2 and just pass them in your query function comma node L R.
Similarly here query + one R comma 2 * 1 R. Now since the return type is int we need to capture the this is the output we will get from our left child and this is what we will get from our right child. We just need to combine them and return left plus right.
We'll get something from our left child.
We will get something from our right child. Sorry too much messy. Uh left and right. You have to combine it and you have to pass it for your parent. Okay.
Now let's try the base case first.
First first of all there's a case of no overlap. If you guys remember as I told while uh explaining the query part if your query is not overlapping with the current range let's say your small L is 1 and R is four but your L is something 8 and R is 10. There's no allow. this range has zero elements which are contributing your in your answer. So just return from there. So how you can check that either this uh this r can be here your l r can exist over here or let's say this is your ln r let me draw a number line this is your ln r it may happen that your l comm r is here or it may happen that your l comm is here there are only this two cases of overlap uh non-over overlapping it will never happen that there's any other case then it will be counted in partial overlap or / R. So there are only two conditions. If my capital L is greater than R or if my capital R is greater than L.
So for R this or this not this both at the same time. Either it may be this or maybe this. Okay. Uh capital L is less than greater than uh no uh I think like this.
Okay, what to return in this case?
What you will return?
Of course, you are doing addition and since this range is contributing zero, just return zero.
Now let's write a case for complete overlap. Let's say this is a number line. Here is my L.
Here is my R. Now if your array range is doing an complete overlap with your query range here and here, you just return that answer because you got the contribution of this part. You have to find for this part and this part. So you will return this. So how you will write this mathematically either your L is greater than equals to this L and this R is less than equals to this capital R.
So capital L is uh less than equals to L and M. Here it should not be odd because there is only one case of complete overlap which is this. Both conditions should be satisfied simultaneously capital written the value which is store in that particular node. Okay.
Uh for example, if your query range is from uh 1 2 3 and you are over here which is generating 2a 3. So 2a 3 is completely overlapping with 1a 3. Okay. So you will just return the answer from this node directly. And for this node its index we know for root node one left child two * node and for right child two * node + 1. So 2 on the 2 + 1 3. So sgd of node. If it is not an overlap case, if it is not a case of complete overlap, then it is a partial overlap. You have to find the mid, put the recursive calls for left and right child, combine the answer and just return it to the parent.
That easy. And this is the complete code for the segmentry.
It's not too big. It's really very very small code. Just 50 lines.
And since now I'm explaining this code to you. So it took me some time to code it but usually during contest uh while practicing I simply code it within five to 6 minutes. It won't take much time once you practice this. I will suggest while practicing the questions don't just copy paste it initially what you should do uh write the complete template from scratch because if you don't write a complete template from scratch it won't fit in your muscle memory and still it may happen that at this point also some people may have doubt those doubts will also get clear by implementing it again and again because it has happened with me uh with my peer group too that some things are not clear in first time But if you code them again and again those things got clear in those things get clear in future. So that's why um simply just code it while solving any question.
Don't just copy paste the template to save your time.
So let's check the query function. SG dot query.
Let's query for comma.
SG do query. Let's ready for L 3.
Uh, okay. We need to pass L 0A 3A 1.
Uh, 0 3 1.
Okay, let's run the code.
So 14 and 21 for 2 3 14 14 10 + 4 14 and for 1 3 14 + 8 nothing but we wait for 1 and 3 it must be 14 + 8 is nothing but 22 + 123. Uh it is printing why is printing 21 0 3 1 1 3 everything is correct. What's wrong? Oh uh okay okay okay we have updated this value now I updated this 8 to 7 that's why okay so this is how you will write your segment and this is the complete code I will put this code on my GitHub repo and I will mention it link in description even I will mention the C++ code too okay um one thing I want to show I wanted to show that see this was for addition Now some of you may ask me how to do this for minimum maximum gcd. What you have to do uh just come here in your merge function and just change this thing add here comma and in Java we have the math class which has the static function min.
In C++ you can simply write uh uh minim uh yeah in C++ you can directly write min of a comma b that simple you have to just change one line um some things you may even change like this was in complete binary tree but the thing is some uh what will happen when you will encounter an array of size uh c uh it's good I like get this thing. Now let's say your n is not a power of two. You'll be not using all the indices from your array.
Till some point you will use indices and after that you will be left with some vacant values. Okay. And let's say you are over here and you will combine some values. One will be from here and one will be from there. And this values are vacant. There's nothing in at those values. In case of addition in Java as we know the default values by default are zero.
Okay. But for maximum minimum GCD those will change your result completely. If you have an eight here and here you have zero let's say let's say and if you combine answer from them two * node 2 * n + 1 your minimum will be zero but it must be eight because your array is ending over here. These are the back end values. So for that's why according to function you have to initialize your array. You can initialize it using a for loop or in Java we have the arrays class which have the static uh function fill which has static function field using let's import the class uh SGT and with what you should fill it now it depends upon the question. If in question you know that your value won't exceed the maximum integer value and now here we are taking minimum. So we will initialize it with a very large value which is nothing but from integer class in Java you can take the max value.
Okay.
Of course if you want to take minimum we will initialize with a very large value and if we want to take maximum we will initialize with very small value. Okay.
So you have a minimum over here. Uh the changes uh these are the changes which you have to remember according to the function in the question. So you have to change the constructor. You have to change the merge function. This things won't change. Uh this things will also not change. Something will change here.
Don't return in zero as I told return integer integer dot max value.
Okay, integer max value and rest of the things will be the same.
Fine. Now the minimum for 2 3 should be four and for this it also be four. Uh instead of 2 3 let's do 0a 3.
Or let's do one thing. Uh let's remove this update line. Let's find an update for 2 3. Put this line over here. And instead of seven I will be putting minus 7. Okay.
Now let's execute this code.
Okay, for this we are getting correct value which is nothing but min - 7 for the complete array because this which index first index will be replaced by minus 7. But why we are getting a garbage value here? The reason is this.
We had to change this also 4.
Okay. For max you have to just change this to max. Here you have to uh change the value.
Then change this function and change this.
These are the changes you have to do according to your uh function which you will implement inside a segment. In case of object segment tree let's say you have to store three four parameters just create a class and instead of just create that class object array over here and write your much function according to that and you're done with segment two. Okay. So thank you for watching this complete video. If you guys have any doubt you can comment. I will definitely try to answer those doubt in comments. Thank you.
Related Videos
Agentforce NOW AMA: Build with React and Salesforce Multi-Framework
SalesforceDevs
490 views•2026-05-28
How agent o11y differs from traditional o11y — Phil Hetzel, Braintrust
aiDotEngineer
450 views•2026-05-28
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
People of Game of Thrones using JavaScript DOM
AltCampus
296 views•2026-05-30
Introduction to Problem Solving Part - 1 | Lecture 1 | Intermediate DSA
ascensionix
107 views•2026-05-29
So What's Odin Lang Even Good For
TechOverTea
131 views•2026-06-01
