Transcript for:
Segment Trees and Lazy Propagation

hello hello hello hi guys ke I hope you guys are doing good in this we're going to see complete crash course of a segmentary again I'll walk you through the entire cabus but the code the notes all that you will get soon on coding.com although not right now it is there but soon around in a month you will have it after this video is posted now the syllabus we'll firstly cover what are segment trees next we'll cover why actually we use segment trees instead we have Fen victores we have prefix sums we have already had one course or one part of fenic trees if you're not watching just you can go and watch it but still if we have these then why still we are using a segment tree what's so special about segmentary then we will see actual implementation of segmentary while going through its Basics then we'll go on to segment Tre with lazy propagation again although many people are scared of segment trees and especially lazy propagation but I swear it is easy as F now easy as e but I'll say next we'll see a generic segmentary template or a code you can say because if you have been following us we have given a binary search template we have given a two pointers template in 99% problems that can be used same way in this you can use that generic template and again with using that template itself we will use 10 problems and same many more problems can we solve just a quick modification here and there and you're good to go no changing code the entire segmentary not required lastly uh I'll give you a quick hint about what is what is a descent segmentary or and and also merge sry right and again 40 plus practice problems you can find here right again the entire code approaches everything again why I'm saying again again but yeah entire code and everything what are the notations used all that is taken from CP algorithms so as to be consistent if you want to practice more problems or if you want to study much more further then you will go and refer the CP algorithms right and that it will help you what you'll study right now now let's start off with our actual segmentary firstly if you don't know I'll tell you segmentary is famous for its range queries again if you will think of range queries then you will think Aran uh we have already seen that range queries can also be solved by using Fen victores and also we have seen other ranged based data structure for example if you don't know this rmq regim query uh we have Spar tables we have prefix sums we have F victory if you're confused on what pen Victory is why I cannot use prefix sums for my range queries then just go and watch this one video link will be in description but if you know okay it can still be solved the same thing can be solved by using my segmentary just remember segmentary is bop bop as in father of every range query available although it is a bit slower than other algorithms again when I say bit it actually incurs some login factors building up extra SPAC is used but it is actually the father now segmentary what is the advantage although we have studied other range data structures but what is the advantage of segmentary firstly it is super duper versatile I repeat I'm I actually added a duper I don't I didn't even know the spelling of it but still I added it is super duper versatile this to know this fact I will go on to it a little bit more further on but it is super duper versatile next is that Fen Victory we always have the range starting from the beginning which means the perix but again if you don't know in a f Victory which is kind of a younger brother of my segment Tre as you can see he has lesser responsibility he has lesser functionality and stuff that's what we see in Fen Tre that okay we are actually starting from the perfix itself if you remember but in this we maintain for every possible ranges the answer is there and the biggest thing if the solution is not invertible which means if you know min max we cannot use a Fen Victory if you remembered we did this problem block placement qual if you don't know what the problem is check the description or write the problem Name by you get the video you will recognize how a Fen vict tree is it's so hard again when I say invertible which means okay if I ask you if you have some range maximum query if you update something and if you want okay my current value is five I want to update it with the three I cannot do it because I can only increase the value I cannot decrease it if I have a maximum same way for minimum I cannot go reverse and we actually encountered this problem in our this block placement queries problem although we have to find some hacks around it but finding hacks takes time and also it is very much typical to actually understanding code while in our case I can say Okay update anything assign anything do anything do a range query of Maximum minimum or anything nothing is coated with each other which means updating a value is not related to quing a value we'll see everything but I'm just showing you what are actually the benefits of segment Tre again segmentary is super flexible data structure what I mean by that is is that I can add I can answer much more complex Problems by simply using my segmentary because everything is so visible and everything is so modifiable that again when I say everything I mean the node structure again I'll go I'll go on it very deeply what I mean my node structure how it is so modifiable but I can answer super complex queries with also segmentary which simply means that a single node can store many values again you'll be very confused okay what is not no worries I'm just telling you what are the benefits if someone ask you last but not least uh one important property before we start on with the actual segmentary is that segmentary requires only a linear amount of memory people just think okay I'm building under tree I will be having many more things which I will S no bro you know that a Fen Victory and other rain page queries they require linear amount of memory same way my segmentary also requires a o of 4N memory again you might be thinking okay why 4N uh why other require o ofn and stuff but no worries we'll go to it also later on now you know the benefits of segmentary let's start off with actual segment tree as we have already had the spoiler that we can do range queries the star Mark is although range queries can be done by many data structures but with updates now re I can find the range minimum range maximum range sum range multiply range gcd range Z range it goes on but okay but where it will go on up till how far what operation I canly no worries I go to later on no worries but the list keeps on like list goes on and on and again uh with updates is a very specific fact why we will be needing our lazy in future but if you don't know why updates is a very why it's a super big thing why I'm so hyped about it please just go and watch this one video in which you will recognize that why prefix sums cannot be used which is very commonly known range based query structure dat structure now you will see that we have these operations I will have update and query I can update any element or any range I can query any element or any range Now update can be anything here in this case let's say zor query can be also anything let's say I take a sum which means I'm updating by saying bro update and do a zor while updating but while quering do a su everything every possible combination is possible so you'll be worried okay Arin but how big is this list there is no list as such the list just simply says any associative operation can be done done by simply using our segmentary what I mean by associative operation associative operation simply says that a plus b bracket + C is equal to A+ bracket B+ C anything which follows associativity will also follow our segmentary rules you can easily say that maximum maximum of maximum of a comma B comma C maximum of a comma Max of B comma C it also follows our associated rule so if in future if you're worried to think Arian uh you never told any problem involving gcd can I apply gcd on segmentary yes you can because it is associative right so any operation you encounter in oper operation can also be made because right now okay these are very common operations but what if code Force problem simply says operation is a function you have to apply a function and that's Operation how will you know if you can apply a segmentary or not this function should be associative then you can apply it okay now we know that what operations I can apply on my segmentary but for Simplicity until I reach on to the problem discussion I will take simple range sum query again for Simplicity I will generalize I will take 10 problems also after that but for Simplicity for entire explanation from segmentary to ra propagation to generic segmentary I will take range some query and again simply I'll give you by examples also with again make sure with updates now let's start off by simply seeing that what a segment tree is the word itself says segment tree you have an input array as you can see this is my input array see input aray is 1 2 1 4 2 3 1 1 input array again index also 01 you take segments or portions of this array and make a tree out of it remember your main name was range some query what I did was I took segments okay I took this segment I take the sum of that three and again I want to make it as a node or tree structure so I made it three I take this segment 1A 4 and then I add it okay it it became five 2 comma 3 added it became a five 1A 1 added it became a two same way 3A 5 added it became a eight 5 comma 2 added it became a seven 8 and seven added it became a 15 so this is what a segment tree is make segments and apply your query whatever you want and that's how you build a tree before going on further this lecture and entire crash course it takes a lot of effort and time to make all these notes and stuff so it will be very helpful if you can just like it and share difference please thank you now so this is what a segment tree is now what actually it is doing U realized very easily but how to build it okay uiz what it is doing but how to build it it's a question right the question is simply it you can maybe if you want you can take pointers you can make a tree if you remember if you have done a tree problems you know you have a left and right pointer you store the entire pointer and structure storing a pointer which means storing some space for that pointer right which means you will store some space for the pointer also which would have taken some extra space does we utilized our one basic funa that how we can design or basically put our tree inside the array itself so I will show you what I did was I made these tree nodes and I numbered them in the indexes of the array I will convert this entire tree to just one single array so as to not use any extra memory because our main aim is to decrease time decrease memory I'll use as minimum memory as possible so what I did was okay I had the node I indexed it at one why one you will see later on but you will see what how it will help me is if I have the index one its left child will be current value again let's say the index value is V its left child will be 2 into V Its Right child will be 2 into V + 1 and the same will follow the and same will be followed by the entire tree if it is two its left child will be 2 into two Its Right child will be 2 into 2 + 1 again it is 3 3 into 2 6 3 into 2 + 1 7 and the same way four it became a eight four it became a 9 five it became a 10 five it became 11 6 it became 12 six it became a 13 7even it became a 14 7 it became 15 so if I want I I can represent this entire tree as an array itself in which one this this at index one it says I am the root and these which means 2 into 1 and 2 into 1 + 1 are my children this two will say okay I am let's say another value my children are four and five thus by simply using an array I was able to represent my tree th using or basically efficiently utilizing my space now we simply saw that okay our root will be at V and we at 2 into V + 1 and 2 into V and 2 into V + 1 which are the actual indexes of our tree now comes the fact that what is the space used although if you had known that this is one this is two this is four this is 8 so at every level I am actually increasing at every level I'm actually doubling up up my number of nodes and this was my input node or input array which is n right imagine it has n nodes so with a simple tree property I can easily say that the entire remaining tree will have again n nodes if I take the summation it will be roughly close to N minus one I can take I can say it will have n nodes roughly so in total this would have ideally required a space of 2 into n but but if you remember in the very beginning I told you the space used is actually o of 4N because we initialize this tree array remember tree array by why tree aray it's a segmentary array I initialize it with actually 4N why is that the case that is the case because we considered the best case scenario where every node is there but I can show you a simple example of not the best case what if you had one again like imagine that you have this nums or basically the input array as 1 2 1 425 or 435 I have only six elements right so while when you start building the tree you will see okay one 2 3 2 4 5 and 3 6 7 for four it will be 89 for five it will it would have 10 11 but for sure I have no notes for six it is 12 and 13 for 7 it is 14 15 so you you can easily see that these nodes are missing these nodes are missing basically not there but still I have to keep space in my array for them but you will say it's a was of space no it is not it is much it is super optimal what we can do considering we're not using pointers which will take super extra space so we realize it is not that enough to keep only two in so I will have to keep more thus because we keep a 4 in as a memory space for us now although a bit space is wasted because of empty cells but that is okay for us that will not give much effect to us now now let's when we have known the entire rough structure of how a segmentary works or how a segmentary is now let's move on to how we will code this thing up firstly before coding up you need to build up the segment Tre although we build up logically but how to build up in the code we'll build up the segment Tree by code now as it's a tree so I assume that you should be knowing a basic tree traversal which is a simple DFS traversal if you know a simple DFS simple recursion you should be good to proceed further if not just go and watch this one we to understand how a DFS Works how I use the property or the information of my children to use them because I'm not good I use my children that's how what what a tree does it he uses his children to get the property for him which is simply performed by using a DFS now proceeding further further if you remembered a while back we showed that I will start off from the index one which will act as a root but if you know you in the very beginning you have only the leaf nodes of the tree which means you have the input AR input AR is the Leaf nodes so this value although you will start off from the root which is at index one but you will build these answers while coming back now we know we'll apply simple DFS which is simple recursion simple recursion says that if you want to perform any operation while while coming back you perform this operation after the recursion or the after the recursive step so what I will do I know I will firstly start off from index one I should be knowing the range of this which is from zero as you can see my zero to my length minus one again if the length is 8 length is 8 so length minus one will be seven so I know this is my range I should simply keep traversing as soon as I reach my end as soon as I reach my leaf nodes while coming up I should build my answer I should build my answer I can say I should build my let's see the code again I will use some basic symbols I should say notations these symbols are specifically used by taking consideration they are in line with CP algorithms this is the only website or you can say the god website for studying and again mostly studying and a bit practicing for CP problems so no matter what if if you study from me if in future you want to just have a quick recap by giving a contest you cannot watch this entire crash course you can watch though but still you can just refer the CPL go.com and you can just get that idea now T will Define the segment tree array you know the tree which we build of four and size the entire tree which we represent as a array that will be our t v is the segmentary vertex which I was talking about so far v v 2 into V and so on so forth so V is the segmentary vertex of this array t cool TL and TR it is the range of my segment Tre which is as you can see Zero and N minus one which is the range input array range I can say now let's build up the segmentary again in the simple recursion we know this is build is a function which requires the input array input array which is this input array right it requires my v it is the index remember it is the index V is the index of what threee v i I require a v i require a TL left which is zero and TR which is right as you can see I have also commented it every code every links will be in the video itself so no worries I will give you everything no worries and again you might think Arin where is the T defined where is the T Vector defined no worries everything will be done go with me now you have to build for building you need these stuff okay okay makes sense makes sense so for building what you do I know the array range I have to reach to my leaf I have to reach to my leaf at every point if I have I in the very beginning I have my ranges 0 to 7 both included I will cut it in half I will ask for 0 2 3 then I will ask for my four 4 27 then again this we'll cut it again in half and we'll ask for this range and this range again half this range this range see every time it is doing half half half and asking for both the ranges when it will stop it will stop when the range length is itself one how will the range length be one only when my TL is equal to tr because the range length is TR minus TL + 1 so if both are equal the range length will be one one if the range length is one which means I have reached the leaf node if I have reached the leaf node just put that leaf node in my tree so in my tree again V is the vertex if you know or you can say index I will simply say bro put this specific again a is the input aray TL is the index you know that I have been by again TL and TR both are equal so you can put a t or a TR both will work but this will work because because I have reached my one single index that is it okay so Leaf node is build up you know that what you were doing you were finding the mid which is TM TM is the mid index by saying you have a TL left TR right you do a by two simply as you do by search you find the mid using that mid you will up you will ask the recursion first saying a a input Vector you are going to a child left child will be 2 into V right child will be 2 into V + 1 with the for the left child the range will be for the left child the range will be TL to TM for the right child the range will be TM + 1 to tr R right so for the left child range will be TL to TM for the right child range will be TM + 1 to tr now when I have done the recursion while coming up while coming back I should compute my answer in this case I told you I'm taking a range sum so whatsoever I have got from the left child whatsoever I got from the right child I should just sum that up and I will take that summation from left and right and I'll get the three so I'll take the summation from my left child for a v it left child will be 2 into V right child will be 2 into V + 1 I'll take the summation of both of them and that is how I will get my answer and thus I was by simply a simple code I was able to build my tree I can say my segment tree now the simple time as you doing a simple simple DFS traversal on the entire nodes of the tree it's just o of n space you have already defined as t t will be defined in the very beginning as forn although you know I'll go to a operations but I have not initialized tree here so you might think okay where where did T come from no worries but so far you have seen the tree is now built now again I just given a quick quick explanation that in the last and you're coming back you would have got the answer of 2 into V which is a left Child 2 into V plus which is right child so you can simply use those to get your parent answer when the tree building is done you are good to start querying for any query which our segment Tre we will use for so let's see that if you have built this tree I ask you to query for for this range from 1 to index 5 from index L to r l is 1 R is five I'm asking you to query it when I say query I indirectly mean give me a Range some query so I am trying to ask you what is the summation now to optimize this query what are segmentary uses is again you know I have in my mind I have to go and search for this range 125 anything outside this I'm not concerned about anything inside this I'm concerned about so what this tree is storing let's take a look again this node is storing the answer for the range 0 to one as you can see this range this five is sh the answer for this range this is showing the answer for this range this is showing the answer for this range same way this it is showing the answer for this entire range this is show the answer for this entire range ultimately this 15 is the answer for this entire range that is how useful my query is why why why it is useful it is useful what if I would have asked you Aran give me the answer for this entire range give me the answer which means give me the range sum for the entire range you don't need to go anywhere just simply ask the root that's your answer if I ask you all right um I might not have but for Simplicity let's quickly jump on to right and see what's happening on right although it will jump on left also right also on right when it will jump it will query for L2 R that's a query which he wanted the current range will be 2 to 3 because of P again mid I will find mid will be 3x2 so mid will be one so right range will be TM + 1 which is 1 + which is two so it will be 2 2 3 is the right range 2 2 3 is the right range and I can easily see that now it is a complete overlap the input range on which I am at is completely lying under the query range which is L2 R so I don't need to go any further I should return from here whatsoever answer I have got what's answer I've got I have got the answer as five so I've got the answer five it was a complete overlap I should return five from here how I know how I got to know that I got to know if I have a complete overlap how to know that by simply seeing see this example L is less than equal to my TL R is more than equal to my TR L is less than equal to my TL R is more than equal to my TR in that case it's a complete overlap in that case return whatsoever answer you have stored at that tree node for me it was a five I returned it what about the partial overlap again in the partial overlap case as in this case I know in the partial overlap I told you I will go and try for both left and right so I will split in the middle which means again TM will be t l + TR R by2 and then again go and query for left which is 2 into V go and query for right which is 2 into V + 1 again in the left the range will be TL comma TM split it at the mid and right range will be tm+ 1 comma TR cool and again simply go on until you find a complete overlap as you can see in this case it will again would have got a partial overlap because the range is 0a 1 the input range is 1A 5 it would have again did went on to left and right but right would have been successful thus it would have returned a two from the right side five from this node and if I just go on it will be five from this node also so I will return but Arian you uh you discussed partial overlap you discussed complete overlap what about the no overlap okay in no overlap case as in this case there was no overlap the range was Zero while I am at 1 to 5 as in this case also the range is from 6 to 7 while I am at 1 to 5 in no overlap case return anything which will not impact your answer so in no overlap case where my TL is more again if let's imagine your lnr is here so if your TL the left of your it is more than your r or if your TR R if it is less than your l in that case return something return something that will not impact your answer in this case the something will be zero because if see you doing a range submission a you're adding a zero this will never impact your answer this is called as a identity element remember this it it will be used a lot when I will go on to gener so you are adding something which will not impact your answer that adding something is called as identity element if the operation would have been multiplication I should have written something should which which would not impact my answer that that something would have been a one because one is the identity element for multiplication now we realize these are the identity element ments they will depend upon the corresponding operation multiplication I have one plus I have zero or I have zero same like it's a simple way saying apply some operation after which element should remain as it is that is called as a identity element and again the operation applied or the transformation used is called as a identity transformation now we have got how we will query our entire tree it is entirely purely DFS no segmentary the people who are scared of segment trees by their name else it is purly DFS so you queried you will simply pass in the initial V which is One initial left hand which is zero initial WR in which is length minus one actual input which is L Comm R you might feel like Aran it is redundant to pass this information I will say you are correct that is the reason in the code when I will show you I will override these methods I will override these methods so that I don't need to pass these at all it is actually redundant to pass them it will always be starting from these values so it's redundant now but the input for me which is required is L Comm R let's see how I will use it I will simply use it by saying that again please don't bash me by saying R in what is V what is TR what is TR the same has been used by your CP lthms also now same way if it is no overlap return a identity element if it is complete overlap return the value stored at that node of the tree if it's a partial overlap find the mid go and query the left side get the answer go and query the right side get the answer when you have the answer while coming up just apply your operation you want the range sum so you applied the summation operation on the left and the right ranges and thus getting the answer that's your range query done now comes on what is the complexity of this range query because it might feel okay you are going on to like nearly all the nodes you went on here you went on here then you went on here then you went on here also to check ideally it's just that you did not go on to the leaf nodes so are you saying for one query you will take off end time no what's happening again the reason I took that example just to show you the worst case possible now what's happening firstly I ask you very quick question what is the length of this or basically the height of this tree what's the height of this tree ask me tell me the height of the tree is simply log to the base two how at every step I am increasing the number of nodes by two here I have one node two node four node 8 node so imagine in total I have n nodes in the entire tree height will be log to the base two okay height is sorted now check what I was doing I was doing I will go on to O either left or right what I mean by that is if I am here I will either go on to left or right but Aran you went onto both sides yeah correct for the root node for this node I will either go to left or right Aran you again went to both the sides yeah exactly I went to both the sides but if I am going on to the left side which means I will for sure completely take the right side in this case when I went on to right here if I'm going on to right side it means for sure I will completely take my left side which means in the entire sub tree of left I don't need to go further thus my claim was at any point of time apart from the root node I'm going on to either left or right in case I go on to both the sides which means one side I will completely take other side I might ignore so you might think are you saying it true yeah it is in this case only when you had this range you went on to again you went on to both the sides because it was also coming on the right side then when I asked you should you go on to right or left you let's say said I want to go to both the sides right and left also thus my claim was if you're going on to both left and right it is for sure you will take it completely considering you also went on to write here there are many considering see the only thing which you have to see is if you going on to right here which means for sure you also again I'm trying to see the worst case possible worst cases as many left and right that's a worst case right so if it has gone to right which means he's saying in the middle half I have something I have something so if I went on to left and again I'm also saying I should go on to left also so I'm saying okay in this middle half I have something in the left he's saying he has something in the right which means this portion should also be included because it's a range query if I have something in the left I have something in the right for sure that should be connected and thus this entire portion will be included for to showcase the example imagine you had this range you know you have to go on to both the sides okay you went to both the sides no worries but at this point if you have to go on the left side which means the entire right range will be included in this point if you have to go on the right side the entire left range left range this one this one would have been included but in this case you will see sorry but in this case you will see I did not go to my left does I will go on to my sorry I not I did not go go to my right this I will go on to my left now again for left I again can have many options I can go on to left also right also but you will see that how I'm restricting either left or right at any point of time I will have only two options and thus I'm not saying two options at every point no every point in the every level I have just two options at Max two options and I know I have login levels thus the complexity of query will be o of 2 into login or or you can say easily as login now same way for this for this example you went on to left you did not even go to right thus at this point you again have two options you can go to left also and again you can go to right also I'm not saying you will completely take it as it is no firstly you will go on to left and then you figure out okay it is complete then you can take it it was different than that of saying blindly as I remembered I took a left here so I took a right here so I should blindly take this because it will for be gled in this case you will see again there are one option two option that's it here I have one option two option that's it that's how I'm saying again for this example at this point I'm not even going here again two options at Max at this point if I'm going to the left I'm going to the right which means this will not be included okay not included and again at this point I'm going to the left I'm just getting this point thus I will have the complexity as o of login now coming on to update uh here we will update single element of my array imagine I have this input array which was the same so far you updated this element at index two of the input are you updated it and said bro it was no matter what earlier I will up update it to a value 10 so I am telling you the point update a single index or a single point should be updated so what we will do simply we will go and find that specific index two we will reach that index two and then we'll update it and then build my tree again so how I will reach there I know the index is two I am currently at a 0a 7 right if you remembered this this is storing 0 7 you you just have to locate where will you find a index two simply do a mid it will be 0 to 3 and 4 to 7 okay that index two which I want to go to lies on the left side so simply go on the left side okay again bifurcated 0a 1 and 1 comma 2 two lies on the right side okay ignore the left go on the right side I'll go on the right side okay 2 comma 3 again split it two and three go on the left side go on the left side oh I have reached my leaf node Now update that leaf node update the leaf node to 10 while coming back recompute your answer while coming back I will recompute my answer which means I will see okay whatsoever value was there earlier no matter what I have to update it so I had a 4 + 10 it will be 14 no M okay now no matter what the answer was here again 14 + 3 I have value as 17 Again I come back update the answer 17 + 7 I will say 24 that is how I can simply get my entire tree by again I did a simple Point update I a single value so I simply went on to my entry at every node at every level updated the root node sorry updated the leaf node and then came back regenerating my tree basically same uh freshing refreshing my values of the node as you can simply see you're going on to one node of a level thus this point update will take a log end time let's see the code code is exactly same as that of query if I have reached the leaf node again I'll show you the constraints or input firstly you need a v index of the tree you need the range for the tree you need the actual this is the actual input you will see okay values are redundant that the reason in the code I will show you I have overridden them but this is the important thing for the input array a at this index ID update with the value value so you will go on and say that okay bro if you have reached the leaf node you are good to update it so update that node tree node with this upcoming value or the new value if it is out of out out of your range do nothing there's there's nothing you can do that nothing here it is identity transformation you are saying if you don't find if you don't find anything do nothing nothing as in identity transformation that is nothing okay if you have partial overlap for sure find the mid do the same recursion on the left and the right with the updated TL and TM and TM plus1 and TR and then when this is done while coming up find the value of your tree which means TV will be I'm doing a range summation so it will be left node and right node summation thus building up the tree back again complexity is off login let's see the code in one go the entire code you can find on my GitHub although right now it is not on the website it is being it is still being built but soon you will see the entire code with the nodes will on the website itself code with.com so nobody you can find from there itself now the code simply I have taken a class again I have not made a function randomly I've have taken a class just so as to make it clean and reusable reusable firstly if you remember you need to make a tree so for tree I take a vector this length is the length which I have taken of the input AR empty Constructor okay I will get the length of the input array this is the L length of the input array a and then I will initialize my length which is the input and also I will initialize and say that e do resize 4 into the length I showed you 4 into length 4 into n we take for Segment trees and then my tree T is built of size 4 and with the all zero values now the first thing which you could do is simply ask this call this function exact same build function which we saw call this query function you can do call call the query function exact same function call to the update function okay but then we realized all these values are actually redundant for us to pass again and again so let's do one sorry so let's do one thing let's write a overridden function so I have written three over overridden functions which this function will only require a build of a and will call my main function which is build function so it is kind of overridden function saying okay it's a and then remaining parameters will remain as it is same way for query I only pass L Comm R remaining parameters it will pass by himself same way for update I will pass only index and the value again this is a point update so single index is only required and then the updation now now comes the actual code how we will use it so firstly let's imagine I have the input array right 1 2 1 4 2 3 1 1 again I have given the size you can find the size from here itself which which means n is equals to a. size you know that build the segment Tre I built the segment Tre with this specific size just to initialize my tree array which is T of size 4 into 8 8 is n and four is my length which I have taken now firstly I just had a simple function call and saying build my segmentary by taking this input array it will build it and again we know the build logic so we so far we have applied is range summation okay okay now simply after building I just simply queried the actual build so what happened after building the query looked like 1 2 1 4 2 3 1 1 again you will see I actually querying every index so I'm query index zero index up to index n so I'm asking my segmentary query I'm not going and asking t0 TI This Ti will be wrong this is a tree you want to query at the index of the array so query simple this is your object segmentary asks the method query and then it's a point update so you ask L Comm R you are given L Comm R but both L and R are same in this case because it's a point query which which means for an index what's the value so I simply get the value okay does use you know the input the input which was this I got the same after querying it exactly same right now simply let's say if I ask you um again range query from range 1 to 5 give me the summation so from the range again 0 1 2 3 4 5 from this range to this range give the summation 4 + 1 5 + 2 7 + 2 9 + 3 is 12 so from range 1 125 I got the summation as 12 this is the summation I have got as sum update okay update update at the index two with a value of 10 at the index two which means at this value update at with the value of 10 now this is a value of 10 10 now again I am again going in query from 1 to five as you can see again 1 to 5 simply you know it was one it updated 10 so technically the answer will increase by 9 12 + 9 will be 21 so this is my new answer obviously the new I have queried the range 1 125 summation so this with this you realized that how did you do a point update and range query build a segmentary a generic normal segmentary by simply using my DFS now don't worry you can apply the exact same stuff for min max zor or and anything and if you want to see the examples and stuff no worries keep following we'll see every example now when the segment Tre is done one thing we we missed we missed what we missed range update we did we did Point query we did we did range query we did we did Point update at index 2 with the value of 10 we did we did not do a range update for which segmentary is famous for being super simple although Fen Victory code might looks small for range updates but it's very complicated to understand and also not much modular you cannot change it like it's versatile for fctory I'm saying range updates right so let's come on and see that we will now start with lazy propagation why the name is given what it is no worries but the entire aim for him is range updates okay so for the range updates take the exact same array if I would have asked you bro please update the range from 2 to5 now don't think of range updates think of Arian has asked you to do a range query on the Range 1 to5 because that will be exactly same as that of range updates but Aran range query is quering something update is updating all the values yes exactly so if I would have asked you update the range of from 1 to 5 with a value of 10 technically if you would have applied the above Point update approach so for this range for every Point inside this range you would have done the above update query that update query takes a login time for every Point inside the range so for me the range length is five so for every five points I will apply a login update so if I use the above approach which I discussed for a point update if I use the exact same for the range update also it will take a of n log in time for one query considering the range length is n but I can have many queries for every query I'm taking a o of unlog in time so for sorry for every update I'm taking a o of unlog in time that's not good right I should ideally take for range updates or for Point update for range query for Point query for everything I should take login time but for updates how it will be done it will be done by simply simulating what a query was doing so a query was only going again if I was doing a query query only go to those value which he needs and we proved it that query will take a login time so I will only go on to those notes where query was going that's reason I told you if I would have asked you do a range query in this range do a range in this range wherever that range query would have gone to I will also go on to only only only and only those notes what I mean what I mean what I mean by that is that if you remember the example simply let's take this range I'm asking you I'm asking you update this range so in the very beginning you know root vertex V equal to 1 range will be TL and TR now for the TL and TR range you will say okay I start from my tree then I will say update this entire high range 2 to7 you know it's a partial overlap and you know how to find partial overlap you already have seen it then in the partial overlap case you go on to both the children's left and right now on this right range we simply go and see it will be the entire range from 4 to 7 my input query or I my input update was from 2 to 7 4 to7 completely lie inside my query or update range as 2 to7 so this is a complete overlap in complete overlap case and in case of query you remember you will not go down you will you will up you will return back from here itself so technically you are saying Arian if I have given you a task to update a value of 10 in this for these all nodes you will not even go onto these nodes you will return back from here Itself by saying bro the value update the value which needs to be updated is a value of 10 and you know that you have to update your child this guy this blue guy he's so lazy he is so lazy he will not propagate this value 10 to his children he will say bro look whenever you guys need it ask from me I will give you so when ever let's say in future I might go and ask what is the value at the index 4 which means technically I will go on left child I will go down so whenever this lazy guy will see oh someone is coming to me now I should give the value to my children so this is the same this is the same lazy maid in the house that she will sleep whole day let's say if some person gave some message or basically let's say XY the person gave came and gave let's say a few vegetables so she kept with her the entire day when the owners came and when the owners asked um I wanted to eat gaja halwa then the maid will go and make it at that point so imagine she got the ingredients many ingredients which she need to made which she need to make she got the every ingredients let's say she got gaja Galva she got many stuff but then whatsoever was required only that she made at that point of time so my this lazy guy will store the value of 10 with him in future if I'm asking for any query to the down values or maybe any update also to the down one which is kind of partial thing at that point I will go and propagate this to my child and and same way as you can see in the left okay on the right you saw it's a complete overlap in the complete overlap case you store the value with you because you are lazy like me so I store the value with me because I'm lazy but as you can see on the left it is a partial overlap which will happen because in this range the range is 0 to 3 0 to 3 and the for me the query was or the update was 2 to7 so it's a partial overlap so again I will go on to my left and right right again in this case it's a complete overlap which is range 2 to3 which lies inside completely inside 2 to7 again in this range I will store the value with me I store the value 10 this also stores 10 thus what happened you did exactly same as that of a range query but for the people who are actually not sure they will see okay these values are not at all updated with the value of 10 they they are not even seeing that value because this made sure that I'm Shing it if in future someone is querying you so for sure he will try to go down if he will go down while he is going down I will transfer him value so why I should spend my energy to transfer that message no if someone is coming to you I will just give him I'll just give him okay bro because anyone who comes in will come in Via me only right so I know if someone's coming to you I will give him I will drop him the message he will give it to you so that it will help us to Simply store those lazy values at these nodes and thus making us solve the update query in our o of login time but what's the use of it the use is simple our updated AR our range update is done and if in future someone queries it so you know on a query I will take a log in time but the benefit is on that query itself while he would be going down to query something he can simply propagate that a value downwards that's it so the effort which update would have taken to himself he delegated that effort to query or maybe to further some random updates that is how our lazy propagation works so how to store it in terms of in terms of computer science how to store it so I will firstly Mark if some node is lazy or not then I will will also store the unprop value in this case this node again how can add which no this bro V = to 1 this is 2 into V this is 2 into V + 1 which is 2 into V + 1 so this node is 2 into V + 1 so that node firstly is a lazy node so I will take a vector of same size 4N because I have to store for every node if it is lazy or not if that node is lazy okay this node is lazy see and what value it stores as unprop value so it will store a value of 10 he bro I'm lazy I'm storing an unprop value of 10 with me now now comes the interesting part that how we Define it you will simply say okay is lazy for that specific node V will be true that's a lazy node as same way unprop update for the node V simply add that value Arin what do you did here simply bro I added the value but why again that can be a very confusing part for many people here let's say in the very beginning I said update in this range the value of 10 so you will simply go and store the unprop update as a 10 let's say I asked you a update this range with a value of 20 so it's a question for the interviewer of basically for the problem that do he want me to assign the update or to add the update so technically for us I will add the update but I could also override the existing update I could also override the existing update so if I would say assign or set which means I'm overriding so I should override this value to my update if I'm saying add which means I am adding the incoming update so simply add that incoming update add that incoming update right so now you're clear with equal to and plus equal to plus is adding the update equal to is assigning or setting the update I'll show with the problems also in future but this is something which many people get confused on now when you have assigned when you have assigned this simply says one thing bro whenever someone is going down either for quering or for updating anything down make sure you propagate this value which is unprop value but I have value of 10 I have value of 10 which means I added I added a value of 10 in this entire range technically if I ask you if this node is 1 2 3 and four so this summation would have been three this summation would have been a seven now if this node would have not come in so this summation would have been a 10 okay uh let's take a verse example let's take a five so if let's say if it is two then the summation would have been eight now I said do a range update 10 if I do a range update 10 which means I'm saying okay 10 is storing this 10 okay lazy okay he's lazy easy upd updated value unprop updated value which is 10 okay which means this value need needs to be propagated to the children but this 10 if he will propagate to the children okay that's good but he will also be modified right I I will have plus 10 on four four nodes so technically this will be a plus 20 this will be a plus 40 so it is okay he will propag at further when something will go down he will propagate that further that is okay completely fine but for this value of T of v it is incorrect right now until unless I updated I know the range length will be 4 to 7 which means TR minus TL + 1 this is the range length and this is the update which was I got let's say V or let's say any any value so I got the up update so this update I need to actually add on the existing value so I simply add a 40 again this is 4 this is my 10 adding a 40 in the existing value so as to okay make sure this value is correct all there is below are not correct why because this is lazy he will propagate when he will find it useful so I will need one more thing which will say update the current lazy node at least so I'll update the current lazy node again this is updating if I would have said aign so you would have simply put a equal to right now I'm saying updating or basically adding so you'll simply plus equal to this is the Range current range this is a value value to be added and thus I need only these three operations that is it and you are good with the lazy propagation you understand the complexity you understand the operations that's it only required now coming on uh what I will do write the code what changes I need to do firstly I need the unprop update Vector which will say which will say for every node of the tree what is the unprop update which they will store so it will store unprop update value same way I will ask for lazy if that node of the tree is lazy or not so the the way I initialized my T same way I initialize my is lazy and my unproper update value cool now again um if you want to add other stuff everything else is as that of the previous code coming on to the change which we will do simply the query will remain as it is it's just that we know on every query I told you I need to push down what laziness if you if if you forgot I told you if let's say I would have queried for this node so I would have come query now when I say query I come on to some lazy node I should push down his laziness to his children so this is how I will use my push down function which means pushing down or assigning the laziness to my children let's see the push down code first so in the push down code I was standing again if you go back I was standing at the node V having this range I need to push it down to my children for the node V the children is 2 into V and 2 into v+ 1 so if I am at the V I should push down the laziness to my children firstly I'm saying push down the laziness to my children firstly am I even lazy check if you are not even lazy bro there's no even point to come to push down right yeah if you're not lazy simply return back if you are lazy firstly you should make sure that now you are no more lazy because you are pushing down your laziness to your children so you are no more lazy so mark yourself lazy as false now when now when we say push down to your children for sure we should be knowing the exact same parameter for the children also for if I am coming from the node V my child will be 2 into V and 2 into V + 1 and the same way his range will be t t l comma TM and TM + 1A TR right the same way I did here TM sorry I will find the mid TM that will be simply mid and then TL to TM and TM + 1 to tr now when this is done okay that was nice but push down what push down the unprop value which was not yet propagated if you remembered I was saying at this node in my unprop update value I have stored a 10 that whenever in future I will do a push down I will propagate this value do the same thing no if I will do a push down I will propagate the value of stored stored at this SV whatsoever at this SV was stored as the unprop value just push it down to your children and when I say children I mean both left and right children now we'll go on to the push down like apply also that okay you push down that's okay but simply pushing down will not make them accept it you have to make your children accept it just simply putting a Coke inside your child mouth that will not make him drink it you have to ask him bro please drink it right that's the reason you have to now you have pushed down your responsibility now it's their responsibility to accept that update to them and Mark themselves as lazy and actually update them also so if you remembered when any update comes to me I update myself right I update Myself by this value I Mark myself as lazy I mark my unprop unprop update as the value same way if I'm pushing down this pushing down this responsibility to my children they also have to follow the same procedure and that same procedure is made in a different function apply so I will apply at this node this update value I can say which means saying firstly I firstly if it is not a leaf node then Mark that node as a lazy node AR and why you have put this condition for leaf node so basically bro if it's a leaf node then there is no point of marking it as lazy because you mark lazy saying that if in future I come to you you or you want to to go down from me you should and I will just put give it to my children that's all the use of laziness for a child who is infant he has no children so whom he will give he will give no one so so if you have reached the leaf node there's no point of marking it as lazy again or because you have no child of the leaf node right that's the reason if it's a leaf node then ignore it if it's not a leaf node then Mark it as a lazy firstly update the unprop unprop upate value of your child again make sure this is now your child because it is a 2v and 2v + one so now you are doing this update again this apply function you're applying to your child and saying bro my child remember your unpopular update you have added a value of value if I I would have said assign it simply this would have gone I would have simply assigned it but here I have added the update value I'll upd add it and say okay bro your unproper update value will be now incremented by a Val but no matter if it's a leaf node or a non-leaf node one thing for sure will be required which means incorporating the update to at least me this unpopular dat says just simply say that propagate to the child right that's what this says this says at least I should be satisfied so what I will do I will obvious this child will satisfy himself his greed his need not in that way uh not in the Mumbai pun case so what he will do he will satisfy the child will satisfy his greed by updating himself basically updating his range or basically his node value with the new update same as what we did previously so this is how you push down your responsibility or your laziness to your child and then how your child or any node will apply that laziness to himself cool let's come back to the query from where we left so here I said okay if I have a partial overlap which means I'm kind of going down if I'm going down from a lazy node I should propagate I should propagate my or I I should push down my laziness to my child I'll push down laziness to my child simply no matter if if you push on or not your task was to query go back to your query query your your query code exactly same as it is as it is update simply again as it is simply saying if it's a complete overlap apply apply that laziness right now you you are updating in the range l2r right if it's a complete overlap I showed you if if it's a if it's a if you go B it if it's a complete overlap apply the laziness right now right now apply the laziness so I'll apply the laziness sorry yeah I'll apply the laziness right now again the apply function will apply the laziness right now on this node V right and then simply return from here itself don't go down don't go down in the no overlap case simply return return with identity transformation here it is empty now in case of partial overlap you have to go down in case of partial you have to go down now while going down make sure you push down if you have a laziness at me so same way as we did in query also if you're going down simply push down so if I'm going down I will push down and we have seen a push down code also and thus exact same code as it is and VOA just a 56 line change a few addition of two vectors and we have written our code for Segment trees with lazy propagation let's see the code in one go again the only thing which is um here is the apply function and again our push down function which is used so here I've just written that same thing I was telling you that it is assigning the update it is adding the update which significantly have a difference by saying that if I assign an update as you can see exact same main uh code I written here I have the input array as one 12 1 4 2 31 1 I firstly printed that array as you can see this array printed then I did a simple range query same as last time I did a update Point update same as last time I again again did a query okay no worries here this is simply updated to a value of 10 again this is updated to a value and you remembered I was doing a addition so updation update it is updating if I have value one it is update add a value adding a value of 10 so I did update I add a value of 10 value of 10 is added on the existing one right again you can see this is the output which you have which you have got if I ask you the if I ask you update the range 2 to 7 with the value of 10 so 2 to 7 range add a 10 okay in all all of them I will add 10 and then add a value of 20 so I on top of 10 I'm adding a 20 again so ultimately I'm adding a 30 so you know I added 30 in this range and thus I got this is the new entire range I added 30 30 30 30 30 30 30 30 added on the existing values and thus I have got thus it is just showcase that this is the addition in the update what if I ask you assign assign the update overwrite the update so in this case when I say override so at this index two I said assign assign the value of 10 so one it became a 10 it got assigned so it is assigned meaning the update and same way if I did ask you okay update with value of 10 in this entire range then I modified it and I said 20 so now the new assignment will be a 20 so you saw I did a 20 assignment to the entire range here that is the difference between addition and assignment people get a lot of confused in this that's the reason I should like I try to clarify this let's see the quote again in one go again the enti codee you can see on my gith repo you can you can start Market I will again this you will see a Sublime snippet if you don't know I use Sublime as my CP editor so the usefulness of that is you just need to write this code let's say segment treor lazy and you will get the entire code if you want to copy this you will simply have a comment on the top and ultimately in the end just copy that portion and you will have it for the force who use Sublime as their CPU editor they can just have import that file and use it in their Sublime library now the code in one go firstly we initialized and got those variables or those arrays then we had our apply in the push down function which we discussed again you can read these comments it is for your um like for your in future if you let's say come back to the code you can just refer those comments also this is the build function exactly same this is the query function having just the only push down change this is the update function having the apply and the push down and then the same overridden function which we had previously and the exact same main code which we saw just above when we were discussing our range update or addition as an Edition as an update or assignment as an update and thus we have done our lazy propagation of segment trees or segment Tre with lazy propagation and the same thing will work for min max or or and everything we will see everything also now let's come on okay we have seen the segment Tre we have just did a tweak and receip a lazy propagation now we will do another small tweak to generalize that segment code if you go a look if you go and take a look back your look back will just make you wonder that the only thing you was needing you were needing to change was kind of these values but Arian um to make it generic you are taking int int as sorry you're taking this t r t as int it was int for you right int but I can take my node because see this int is a node of a tree that can be a pair also that can be a vector also so now we will try to make this entire stuff as generic as possible but the prime operations imagine that you have a note imagine you have a tree Now give me what are the prime operations you will require for it I will ask you the prime operations will be firstly you can merge two nodes why why is this the prime operation the prime operation for you is if you do a query or if you build a tree while coming up you should apply some operation to merge your two children right so my One Prime operation which I use both in building query and update will be merging my two Leaf notes to receive myself so let's say I have a left child I have a right child I will merge them by some logic and will get a v now that some logic will be my merge function so in this case so far we had been getting a left we had been getting a right right and then adding that up and thus getting us a v so imagine you have a left node imagine you have a right node simply add them up and you'll get a v right okay apart from it what is something else you must be knowing right now which is update now for update there were two major stuff if you forgot for update there were two major stuff where is the code bone yeah firstly is combining the update first it is combining combining the update as you can see here the update is combining which means adding in the existing update the next is applying the update on the node right I'll use the exact same stuff so I know I have to combine the update I have to apply the update so if let's say I had update one coming in okay I have that update let's say I have update two coming in I know my combination logic is saying add the updates coming in so I will add the update if my combination logic says override or basically set the update so I will simply would have set the update to update 2 this is my combining logic now after combining I should have a applying logic now if you had got this updated value whatsoever apply that to the current node of the tree you remember T is the pre node for us so I will apply that update on the current node that is the applying logic so these three are the only logic which we have to change that's it that's it that's so beautiful right so we realized we figured out these are the only three logic which we need to change so we will separate them out from the entire code and then we will build the generic code now I have been speaking enormous times about the identity element and identity transformation now they will be used because now things are becoming generic if I will repeat once again identity element says do apply some operation on it it will remain same so if I do a x x + 0 I will get a x identity transformation on X is let's say x if you have to combine something on X add like have a zero on combination you you get again get X so adding it's a transformation you're doing it's a identity transformation which you are doing here cool let's see what we need we will take a node class again I've have taken node class the use case why I have taken these classes is they can be generic as like you can use them you can make objects of them but that would not be required because C++ is very awesome you'll see how firstly I will need a node that node will store the node details if you know this is a tree for me this is a one node so far this one node only contained one value which was V and that is int same way I have done here also again you might see I have written public in overall I usually give public I I know it's not a good oops practice but it's no worries it's not a oops video it's not a it's not a design video so please ignore it uh I have made public I might have taken struct also I know it's completely fine but yeah I love classes I don't I don't know why so I took that one this indicates for this note I have these values V it can be variable also I could have had a vector of int also inside that one node which means every node is containing a vector of int Vector of int Vector of int that's the beauty of it okay great but so far let's say I have one I'm just replicating this generic function exactly same as that of the above code of lazy propagation although we will discuss the more variations I will have minimum frequency all that stuff no worries but this is what we have taken now this I you'll see okay it's zero what it is you'll see but so far we have seen that we have empty Constructor which will initialize that default value with this identity element you can say now this is a Constructor which you wanted if you want to initialize your the value of Val so get this value of Val initialized then it's your merge function which will have incoming node left node incoming node right node you will merge these nodes and we get the new node V that's a merge logic so anytime you need to do a change you need to change this identity element right you need a m again that's optional you could be wanting to change your Constructor when you initialize that Val and highly likely you will be changing this merged function so in the code you will be only needing to change these three values again for this node okay that node pass that node part covers our merge logic roughly what about the update okay for that I will have update as a class in which I will have identity transformation as zero in the very beginning again same empty Constructor same I I initialize with the empty value let's say value of a v if I want I had a combine and apply function if you remembered combine says you will get this this you will get some other update this some other update you will get and then you will apply this other update on your existing value or existing update whatsoever you have taken this is UN propagated update if you remembered so this is same way apply same saying for the other again remember this other is the newest update which I'm applying right now so I'll apply other update on my current V right same way applying apply this current update basically apply this current unprop update value to your current node V so I had a node which is our above node class I will apply that inside and we'll get the answer okay update done node done everything remain exactly generic so in this also we realize we need to change either our identity transformation or we can or we should change our update Constructor or like and our combine logic and our apply function so these are the only seven changes which you would be needing to would be needing to do in primarily most of the cases now comes the part where this tree is now generic or the segment is now generic for for C++ folks to make things as a generic we have a template saying I will have a node and update again these have no link with the above node and update no worries these are any names you can give any names you can give this ultimately indicates that whenever this segment tree is called so I will call this segment tree then I have to pass in two I have to pass in two something two objects whatever I pass in that will be considered as a node whatever I will pass that will be consider considered as a update so here you will see I will use many stuff I I'll use update I use update do apply so if while initializing your segment tree I'll say Okay seg tree oh I should say St let's say I should say St while initializing that segment tree if you pass something absurd which do not have a apply function or a merge or a sorry where is gone or a merge function if they don't have it for sure it will give an error so it is simply saying that whatever you are putting here this should have this should have a v this should have a uh simple merge function this update says it should have a v it should have a simple node like or I can say apply function or combine function right now coming on back same segmentary code earlier I had this no worries I just added identity element and identity transformation if you know for node I told you I need identity element update I need identity transformation so I just simply have that in the very beginning I initialize to a Mt identity element if it is empty Constructor it will simply go and assign with the value of zero thus I told you that this indicates our identity element same way for transformation update Constructor called it will go up and it will assign my ident transformation as a as a zero again now apply function if you remember apply function same exactly same now we'll just use our object which which we have made the UN propagated update which we had because if you remember this is the Vector which we had this unprop update it's now the vector of update which is this update and this update is actually we will pass in as the update class which we have now this name can be anything this can be update to node to I just have to make sure I I should pass in here as has node 2 here as update 2 while initializing my segment right now in my unprop again uh yeah in my unprop update for this node earlier I was simply combining manually by by by writing a plus equal to right if you remember but here I will ask my combine function to combine it for me I will pass in again this update you will see the flow later on but I'm just keep focusing primarily right now on apply and push down then I will show you how this update is pass all that stuff but you will simply pass in this update you will pass in the range and you will simply go and tell bro simply combine this update on your existing update so you will go and ask your combine function your combined function will say bro this is the existing or the newer sorry I should it it is a newer update which is coming in I should apply this newer update on myself this is a newer update so if I come back I'm simply saying this is the newer update you should apply if I if I yeah it is a new update which I should apply on this node V now after combining the ex the newer update with the existing update I have got the value Simply Now now Simply Now say okay bro whatsoever update you have got apply that update on the current node which is TV I will apply I will firstly get this node and then for this node I will apply as you can see this is the apply function apply logic you simply apply this existing V whatever I had I simply apply it on my current node V and I'll get my answer so I simply applied my current my on my current node I simply applied that and I am good to go now when this application is done your main apply again apply apply you might get confused but this is updates apply this this is your segmentary apply this segmentary apply is used in your push down if you remembered how simply push down same if it is not lazy return if it is lazy then firstly make it as a false find the mid apply on left and right apply on left apply on right now apply on left what apply this uniate value same way again when you pass in a value to a class it automatically goes to your Constructor that much C++ you should know now when this application is done make sure to put your default value of unprop update to a if you remember you you were earlier putting as a zero but now you know you will put as a identity trans transformation which you have already initialized above cool the same thing as a change will be done in your build but you know you can build this Vector out of any array earlier the array was a integer Vector but now it can be anything so again I made a template type will be t t then made sure that same code exactly same code of build same code of build is just that while merging the two nodes call your merge function on this node V so I will say this is my node this again this TV is a node if you go up you will see this Vector T is of type node and this node we have initialized with our node two and this node two is our this node node two cool so if I come on back I will say just ask a merge function I will give him two child node no he just have to merge it so he will come on to your merge function he has got two child nodes and again child nodes by whatsoever logic I want I can just merge those two child nodes and I'm good to go okay when this build is done let's come on to query query exactly same if it is outside if it is outside my query return the identity element strike why because I want to return something which should not impact my query and that is my identity element now if it is in bounds completely in bounds it means completely overlap simply return the node value now for partial overlap make sure to push down first the code we already seen exact same code but while coming up make sure to not do a addition manually but ask your merge function to merge your left node and the right node and this is the left answer and the right answer is the it's the nodes for us they will return me node you can see I returned a node not integer now cool and ultimately return the node not the integer same I will do for range updates also again same for range updates if it is a completely overlap completely overlap simply apply simply apply this apply will go on to your apply function which will firstly combine my update and then apply that update so I simply called my apply the only thing which you will see is I have a update called update called if you remember earlier when you are calling your when you are calling your range updates range updates you would pass in a value so from my main function if I show you I would pass in a value of 10 this 10 value will be passed to my this function LR and update 10 now a 10 value comes onto a class it will be initialized by a Constructor Constructor which we have defined and will up and we initialize the value V of update class with the value of 10 and thus this update is now basically saying I an object having a value of having a attribute or or a you you can say variable having value of 10 and thus it is being propagated to the update function here everything is constant passed by address so nothing is changing here at runtime whatsoever I'm passing in I'm not picking any copy at all I'm passing in the same constant objects constant is just that it is not modified and addresses to pass in by address and not by value now now I will simply have applied that update on my current index V now this application apply is done again this apply is the segmentary apply and make sure the segmentary apply calls in the combine function of update and the apply function of update now again if you if if you go and look back very very very uh you know very deeply you'll see it's a update if I will call for this update in my value it is being passed as a constant so if I am for a constant I'm calling an apply it should make sure that it is also constant that's how that's how small uh this like things in C++ are now coming on back uh we know that we will simply apply the update when this apply is done again if it is is no overlap simply return that's no point if it's par overlap push down while coming up take help of your merge function exactly same as that of your query you have done now over overden functions exactly same it's just that now your build will need a type name as T because you need to build in with the arbitary vector it can be a string also now query and range updates same as what we have seen previously it's just that it needs a update which I can simply pass in a value also and update it's a simple Constructor right yeah now let's see the code how we will code it Vector same as it is just that by initializing my segment tree I need to pass in node and an update now the beauty is that if you have one segmentary which needs let's say range merge operation and range or basically addition op if it asks you uh give me a summation of the range and if it asks you I will give you a update and you have to add that update in your range okay for that I will use this node to and update to if let's say on the same problem I ask you that bro I have to pick one more segment Tre which will do a or in the query and zor file update then will you make the new segmentary no you will just make another node three and update three as the classes and then when you have these two classes having again having all these required attributes which you want you will just make another segment Tre saying I will make a segment tree having a node three and update three I will name it as a segment tree 2 and that is how I can use the segment Tre to in my answer in my problem that's how I can use 2 3 4 five even n number of segment trees in my same problem I just have to make new node and update classes that's it that's it now coming on back I'll build my a everything will make sense because it is integer right now even if it would have been a string still this build would have worked because it is generic on T type cool now uh exactly same code as we had as we had seen previously exactly same code let's see that how the code changed or how the answer will change considering what we will change so again as I show you I will only change my note class and up class everything 95% of time will remain static I'm not saying that your main segmentary code will not be changing it can change but very less so as I showed you let's say I ask you do a range addition but the update will also be added so I am doing a range addition I know when I will merge my two nodes I need to add them up I need to add them up l dot like left do V again if the value is V if you remembered in my node I have put the value as V so the value stored in the node is integer value which is V so it will be left do V and right do V so if I'm saying asking you do a range query obviously do a range submission so you will simply merge by merging you will do a range submission that's what you wanted okay for update I'm asking you do a update you have to add in a value V you have to add in let's say any update value let's say Val in your range it is a addition of update so you will see I have done an addition of this again this other B is the new update which is coming in and thus I have applied that update also here in this node cool thus you will simply see that I did a apply apply so apply one added one added 10 became 11 then I added a a 10 and then a and then a 20 it became a plus 30 in all of these nodes does you can simply see this is the only change which I need to do if I if I would have asked you do a set do a set of update so now I have set my update I'll do exact same stuff now the it has set to 10 it has set to all 20s that is the exact same problem which we have seen so far now we saw everything for the generic piece of code also now if you want to look at the entire code at one glance it is exactly the same code which I showed you right but there's one a bit extras which you will not be hearing but still for extras I will just tell you that there is called as a descent in segmentary which is same way saying if we want to do a binary search on segmentary then we use a descent again we not go to it we will not go on to it um if you want to study it you can just do CP algorithms and you can just check out there check out there because it's not that use like not that much use but still um internally if you go and look you can still implemented we also have a merge sry it's just simply camed and easily via our uh segment Tre which we have built above it simply says that you have few nodes while building the tree again the nodes are not just one integer it's a vector of integer and I know a generic Cod can handle a node inside the no I can also have a vector of integer also so here I have Vector of integer it's just that while building up the array I am actually sorting them up it is being sorted while the array is being built as you can see it is T it is a merge sort tree which is the same V of merge sort the use scale of the problem which it brings in that you have given an input array ER as you can see input array 152 fun input array you're also given the queries of Type L Comm R and an extra attribute or extra variable called as cap your task is to find the number of elements in any range L to R such that those elements are strictly more than or strictly less than your C again it's a simple range query if it's a complete overlap it's a complete overlap apply a simple binary search on this input Vector B search by simply saying up upper bound and lower bound binary search and get the number and simply return that number if it's a partial overlap simply go left and right that's how simple is it simple it is that in a partial overlap go down for sure in complete overlap apply a binary search on that Vector which you have stored in your node and then try for Again by sech you can Implement yourself also or you can simply do a low upper bound also and then if it's no overlap then simply ignore now you are completely done with your segment trees let's let's have some I will discuss nine practice problems using the exact same code which we have seen and then one just last showing okay they can mul possibilities and then ultimately I give you some or you will see 30 40 practice problems for you to do also now again um the code you can find here for this specific practice problem for the remaining ones you can easily find on my GitHub repo the code is generic code generic piece of code it is that only used cool now for this problem how it is special it will cover that a node can be anything here I asked you you have to find the minimum in the segment minimum in the range and also find the frequency of that minimum whatever is there in that range so you have to maintain two things firstly the minimum value and also maintain the frequency of that minimum value just to be more precise the operation says that at an index I I will give you a value V you have to set see whenever you read this you should ring your bell how you have to optimize your or how you have to write your segmentary code right you have to set the elements with the index I to this value V cool again this can be a range also I will discuss both of them although in this question I have given you let's say you are modifying the index I with the value V but I will show you how you can modify the entire range how you can update how you can set the entire range with the value V I'll show you both of them the next operation is in the range L Comm R I will ask you to query and the query you should return me the minimum in that range L Comm R and also the value or basically the frequency the count of number of elements who is that minimum so we realized that how should our node will look like our node will look like by saying in my node I will have two variables now one one variable will be minimum or basically integer again depending upon the constraints of the problem you should Define again as you can see the V for me update is 0 to 29 depending upon these constraints you should decide your identity element or you can say the minimum element for you so I told like I told for me I in my note I need to contain the the actual element which means the minimum value and the count of that minimum value both are integer but I need two values now if you would have written The Code by yourself then you would have to modify your entire segment Tre by taking a pair of in comment but now you have a simple class take just two variables or you can take a pair also it's totally up to you but you don't have to touch the entire code just touch the small piece of code and you good to go and same way I will have on the right as minimum and count when I will merge it I will again get a minimum and count but how the merging will look like merging will look like okay minimum will be minimum of the left child and the right child will be a minimum so my minimum will be this minimum will be minimum of my left which is L do M minimum and right do minimum cool now what about the frequency of the count simply the count if if this minium again let's say if this minium was a two minimum is a two count is three minimum is let's say three count is one so I will simply say if this minimum is same okay copy the count three if let's say if it it would have been four simply if this three copy the count one simply copy the count so if my minimum is equal to left minimum just add that left count in my count if again this this is not else if this is if if it is equal to my minimum again if my right minimum is equal to my minimum then copy my right count why it is used Aran it is used because what if both are three minimum is three but the count is 3 + 1 4 that's the reason I have added if if condition okay my merge function done sorted simply combine function you have said set the value so the update the other update which will be coming in I just have to set as you can see this is equal which is set I have to just simply set that other update to my v and same way just apply that update so whatsoever V I have simply apply that update simply apply that update how simply by saying that I will have my node I should firstly set the value to V it is a setting value which we are doing it is a value which we are setting so in the node I should set the value as V then I should make my count my new count will be TR minus TL + 1 because this I am setting for this entire range if this range had the count of four which means I had four elements having this minum value let's say one is the minimum is is the minimum value then I am setting it to I'm saying okay now the minimum now the value is minimum is four sorry eight value is eight still the frequency will still remain four right that's the reason I am doing a TR minus TL + one cool does this is the only thing which you need so let's see the code that's how how soon we reach the code the code simply says that firstly we will initialize with identity element for me V or this is the minimum value it needs to be minimized so I initialize with the maximum value that is that that it does not affect my answer same way for count it's identity element is zero because it because a count of zero will not affect my answer then the Constructor when you received a value okay update your value with a value and you have got one value so make you count as one okay your merge function you have left and right write the same code as it is same code update function now your ID transformation zero because simply it's a set you can simply have by default of a set as zero in the beginning then you can just simply keep on setting it as you set some value just simply update that okay so Constructor will have the value itself the combine is setting the value so it is equal to the apply also is setting the value so it is equal to on both sides cool and that is how it will work both for your point query for your point update or Point set also and range set also this is the only change which you required to solve solve your answer cool again remaining quote remain as it is let's see how the main function will look like firstly exact same exact same I had I just printed the exact same array then I said that bro do a range query from 1 to five so 0 1 2 3 4 5 five from 1 to five in this range what is the minimum minimum minimum is one what's the Frequency frequency is one so minimum is one frequency is one okay done then update the again it's a point update but range update will work also because it's a simple lazy propagation for us so two at two which means add the index to update with a value of 10 again this is a setting of a value so it actually did a set now this is my new array which is there now again I'm asking for a question query again query from range 1 to 5 what is the new minimum value in the count now this is the same range from 1 to five but now in this case as it is updated the value 10 the new minimum is two and the count is two new minum is two count is two okay then again uh do a range update two to two as one which means index 2 to index 2 I updated that to a value one index index 3 to index 4 again as one index 3 to index 4 again as one I did the update now in the last query I asked bro from 2 to five give me the minimum and the count from two to sorry from 2 to 5 2 3 4 5 2 to 5 give me the minimum and the count minimum is one and count as you can see is three that is how I have simply used again you saw that I only used I only changed these two nodes and got my answer cool now let's see some other code other problem we had already been walking through the range sum query and range updates so this is already covered while you are seeing other could have been a range minimum query which is again the little brother of my this problem it's just simply remove the count all together you don't need count at all that's how you can simply solve it which is range minum queries what about I ask you you have to add to this range L Comm R again I would have written the uh L and R but it is same as that of what we saw in problem one the constraints are all same as that of problem one cool now add to the range L Comm R and then another is find the value at the index I okay I'm saying adding to the range l comma R what's simply adding adding is simply updating updation updation is actually addition now so this is now addition the operation is now addition and then find the value okay it's simply a query now for a simple query uh you might feel like I there is no merge operation which he's asking me to do yeah correct so you can just put a by default merge operation anything which whatever you want here I just put a plus if if you want you can do anything because he's only okay batteries dat because we can simply use any merge operation and that will work for us because we are just quaring for a simple Point although if you would have asked for a range qu then you could have just WR okay if they want the sumission just do the summation they want the maximum to the maximum all that stuff cool that is we done with the problem number four problem number five it simply says set the value V in the range L2 R by the operation AI is actually maximum of AI or V it is not setting the value directly to V it is setting the value to whatsoever is the existing value higher okay that will remain as it is if the incoming value V is higher it will become V so that's how I'm setting a value V based on this condition that's a different thing right yeah and for the query you have to find the maximum value in this range L comma r now if I check for the update it's simply assigning the update so I'll simply assign the maximum of existing value and the newer update coming in to apply the latest update I will simply apply the apply the latest update by simply maximizing the existing value of the node and the new V new value update new value of update now for query you now you want maximum value of this range L Comm simply you can take that v as zero considering your minimum value zero itself if not then take as minus infinity of minimum value cool just take the maximum take the maximum out of both of them and that's it all set cool now for problem six it say is that you have a range you have to assign the update on this range L Comm r with this value V straight forward assignment so I'll simply assign this update in this range and I have to do a range summation so I'll do a range summation that's it next problem add V to the segment but find the minimum of this segment okay I will add V again this is addition of v in the segment addition of v in the node and finding the minimum so finding the minimum merging is actually minimum okay next problem multiply all the elements in the range L Comm r with this number or the value V and this is the update operation the query operation is find the sum of the elements in the range L Comm R cool so multiply which means how we'll combine it we will have the V we'll multiply our latest incoming update with a V make sure that depending upon what the problem is saying it can overflow depending on what the constraints are so for me right now let's say I'm saying if it overflows have a modul with 9+ 7 so I will have existing V I multiply with the new incoming update and I'll do a mod same way I'll apply that on the node with the existing update I will simply in the existing node value I'll simply have this V multiply and do a mod again for my summation of elements it's a simple summation of elements that's it again mod I have done it every step you will see else this is my update this is my note cool now problem number nine it simply says apply the operation AI equal to AI or V is a bitwise or if you don't know to all the elements in the range L comma R and then find the bitwise and of all the elements in the range L Comm R so the query is asking for a and so I'll do and in the query while the update is is asking me to do a or operation on the existing value on the existing value I'll do or operation and same I will do for my node and th get my update done now this same multiple such combinations can be there assign the update the doain query maybe do a set of your Min value and do a range addition so now it can keep on going now for you these are the practice problems which you can again link will be descrip in the description below or you can just go and visit code that in in that also you will have the entire documents again probably in a month because that is still in a building phase I hope you guys liked it if yes then please do smash like button please please please to share with your friends so that the reach grows and it can reach to more people and more people can take advantage of it and yeah thank you so much for watching goodbye take care bye-bye please like it if you liked it if not then okay you can like simply dislike it but if it was helpful pleas like it and please comment and tell me what you learn from it bye-bye take care