Dude, your explanation on these complicated algorithm is so clear to me compared to other youtube channels. Still super helpful 7 years later and I really appreciate your time and passion.
Your tutorials are the best as usual. I was struggling with the simulation part of lazy propagation. Thanks to you things are clear now. Please take out some time to make a video on Lowest Common Ancestor. Thank you for your hard work, really appreciate it.
I am preparing for interview at best IT firms. Your videos are best source of learning than any channel i ever visited. Thanks a lot and keep teaching with such a great dedication and ease :)
difficult topic explained in easy way. I don't know how many are there who watch your coding part but for me i always stop after your algo explanation.
this video is cool. :D perfect and clear explanation easily understandable . thanks for this and i expect some more that could help understand data structures that generally used in competitive coding
I am a fan of your videos! Could you please explain somehow "Find the median of two sorted arrays in log (Min(m,n)) time?" I've really had a hard time in understanding this solution but still couldn't understand. I look forward to you for this.
Thank you for this great explanation! :) But, what should I do when I have to divide leaves by different numbers? (for e.g. let's say, I have to divide elements 1 to 5 of input array by Least Prime Divisor of that particular number)
Bro i really appreciate your hard work but about those data structure which is not taught in our B.tech syllabus such as fusion tree, AEB tree which is more and more faster than these tree 😔😔😔 and that's why we didn't get a job in the company 🤔🤔🤔
Hey Tushar, how are you doing? This Friday I have got my first online code screen (90 mins one) with Amazon, Can you please share some advice on topics I should cover? and how I should go about it? I have learnt a lot from your sessions on you tube, thanks in advance and have a good one.
What if we have to update an interval with different values , for eg. to add i to an interval [l,r] where i is the index of the respective element to which it is added.
okay then i think we update node value as node[l,r]=(l+l+1+l+2.......r) and lazy[2*n]=(l=l+1+l+2...(l+r)/2) and lazy[2*n+1]=((l+r)/2+1+.....r).in short we can write formula for node[l,r] as sum of AP terms and reduce in beautiful expression ,cheers!
hey man! awesome explaination! could you help me in some other scenario? I have max range queries which i can deal with but for updates i dont have increment updates but updates related to factors of a number so i am not able to think on how to apply lazy propagation there. could you help me out?
At 14:49, we have a condition about low>high but if mid = (low+high)/2, then why would ever the value of low be greater than high. The condition seems somewhat useless? Am I missing something?
You are right, low>high will always be false and you can remove the condition if you want. That statement is a simple check at the last leaf node in the segment tree at (n-1,n-1) where the function COULD make a recursive call to its right side (we know this wont actually happen though) and therefore its just added in as a sanity check. Although Tushar does mention while going through the code at 14:51 saying "at this point it doesn't happen" which is very misleading because it implies that there is a point where it could happen which we now know is not true. Cheers :P
hey i wanna ask if you got a video that explain the " balanced binary search tree " which solve the proplem like if you got Q query and in each query you got left and right and you must print the most Freq(the value that appears most) between left and right inclusive
if after incrementing from [0,0] to 2, we do the query to find minimum between [2,3] then according to your concept the answer should be 5 but the actual answer will be 1. Please justify it. I am highly confused.
SegmentTree[pos] += (high-low+1)*Lazy[pos]; I have seen a C++ code of Lazy Propagtion where the above line has been used while updating the "pos"ition of the Segment Tree when the value at the same "pos"ition in the Lazy tree is non-zero. I have run that program with the same input and getting the desired answer. Can anyone tell the meaning of this line and why it has been not been used in the video?
what if, we were required to update ranges (and not know which element is minimum in that particular range) before printing the final array. How would the algorithm change then to get better optimization.
There is a huge array with all elements set to 0, initially. We are required to update portions of array (from some left index to right index) multiple times. If we choose to do it over loop (brute force it) complexity would be O(N square). How do we update it optimally? example arr[10]={0}; update [2,7] by 1 update [4,10] by 2 update [3,4] by 3 and finally, print the array: 0 1 4 6 3 3 3 1 1 1
Hello bro!...I am you, from the past, when you'll see this comment after 5-6 years✌️.. Just wanna say, everything will be alright bro. And you'll realise then, that the time right now was not that tough than you thought in your past
Dude, your explanation on these complicated algorithm is so clear to me compared to other youtube channels. Still super helpful 7 years later and I really appreciate your time and passion.
people come and go, but their contribution remains... this channel proves it... Literally even after so many years, his vids still helping people
The whole italian community of the IOI used this video to learn Segment Trees.
This video enables me to fully understand the concept of Lazy Propagation. Thank you!
Really man hats off to you..able to understand in one go!!
This is the best explanation of lazy propagation on the internet!
Thanks mahn, keep up the good work!
Your tutorials are the best as usual. I was struggling with the simulation part of lazy propagation. Thanks to you things are clear now. Please take out some time to make a video on Lowest Common Ancestor. Thank you for your hard work, really appreciate it.
I am preparing for interview at best IT firms. Your videos are best source of learning than any channel i ever visited. Thanks a lot and keep teaching with such a great dedication and ease :)
Thanks a lot Tushar.
I have been searching a video lecture on segment tree for months and now u have done this.
Great explanation. GOOD JOB !!!
Your videos are awesome Sir!..Very much easier to understand than TopCoder tutorials!
this all, 8 yrs ago.
gotta appreciate the 1080p res and the screen sharing at that time!
Your explanation is pro level! It helped me so much to understand such a difficult concept.
Thanks, this is one of the best video tutorial of lazy propagation in youtube!
Thanks for great video Tushar. Your explanations are incredibly helpful !
Very informative channel Tushar. Feels great to realise (after seeing your LinkedIn) that you did your bachelors from MNNIT as well.
Excellent explanation. Thank you sir. You made actually a diffucult topic to an eaay one with your clear explanation
its quite good explanation of lazy propagation.....thanks ..
You are the man! Can;t have a better explanation than this.
Bhaiyya video kaafi sahi tha... Especially wo effects
Finally,lazy propagation! Your videos are the best thanks.
difficult topic explained in easy way. I don't know how many are there who watch your coding part but for me i always stop after your algo explanation.
Hey Tushar! amazing work. you make people understand the concepts.
One request, can you please make a video on persistent segment tree?
Understood easily from this video. Can you also provide complexity analysis of these functions in the future videos? It would be very helpful
Thanks for the simple explanation, it helped me a lot!
Such an awesome explanation with examples.
Tushar really appreciate your work. Thank you!
Thanks man for this video..
Now i am able to solve the problems based on lazy propagation
This dude is legend!!!!!
The only video I understood about LP
It's still nice even it has been 4 years since the date the video was uploaded....
Thank you so much man, you are the best.
the best tutorial by the best teacher thanks a lot :)
ABSOLUTELY RELIABLE
this video is cool. :D
perfect and clear explanation easily understandable .
thanks for this and i expect some more that could help understand data structures that generally used in competitive coding
Your videos are really helpful..Thank you very much n keep up the good work...
Thanks. Very useful and properly explained.
Thank you sir....for making such a useful video....
Awesome Video for any beginner in segment Trees !!! :)
Great explanation, and thanks very much for the code, it was very useful
I am a fan of your videos! Could you please explain somehow "Find the median of two sorted arrays in log (Min(m,n)) time?" I've really had a hard time in understanding this solution but still couldn't understand. I look forward to you for this.
fantastic! thanks a lot
thanks for the video, keep uploading new videos it helps very much...
Looking forward to your update.
Much needed tutorial ..thanks Tushar bhai... Can you make a video on Mo's algorithm and how it is compared to segment trees wid lazy propagatn.
lazy prop feels like a bureaucrat came up with a algorithm for seg tree
Excellent Explanation!!
Your videos are amazing..thanks a ton sir.
Thanks man ! ...Awesome lectures !!
Thank you Tushar!!
this tutorial is awesome！as the title segment tree made simple
Awesome one!! thank you very much Sir.
Great explanation....thanks
Awesome explanation
is if(low>high) return necesasary? great video btw
Thank you.....Great work.!!
Only one word! Amazing!
Thankyou sir....The video helped me alot
Great lesson!
Thank you so much !
you really, nailed it!!
awesome Video.... and max here meant INFINITY right??
Thank you so much.
Thank you for this great explanation! :)
But, what should I do when I have to divide leaves by different numbers? (for e.g. let's say, I have to divide elements 1 to 5 of input array by Least Prime Divisor of that particular number)
I want to know how much your coding improved in these three years?
Nice Lecture.
Have you made any video on Binary Indexed Tree(BIT)?
nice. finally i understood lazy :)
awsome explanation :)
You are Too good bro
Beautiful!
thank you so much
Bro i really appreciate your hard work but about those data structure which is not taught in our B.tech syllabus such as fusion tree, AEB tree which is more and more faster than these tree 😔😔😔 and that's why we didn't get a job in the company 🤔🤔🤔
thanks man ,you are great..
Nice Posting! Thanks
It is very hard algoritim.
Hey Tushar, how are you doing? This Friday I have got my first online code screen (90 mins one) with Amazon, Can you please share some advice on topics I should cover? and how I should go about it? I have learnt a lot from your sessions on you tube, thanks in advance and have a good one.
how your code screen was?
What if we have to update an interval with different values , for eg. to add i to an interval [l,r] where i is the index of the respective element to which it is added.
okay then i think we update node value as node[l,r]=(l+l+1+l+2.......r) and lazy[2*n]=(l=l+1+l+2...(l+r)/2) and lazy[2*n+1]=((l+r)/2+1+.....r).in short we can write formula for node[l,r] as sum of AP terms and reduce in beautiful expression ,cheers!
Can we store the minimum index instead of the value and still use lazy propagation technique?
please add one video for " updating values in segment tree "
i think this itself is an example of updating segment tree
good job!
hey man! awesome explaination!
could you help me in some other scenario?
I have max range queries which i can deal with but for updates i dont have increment updates but updates related to factors of a number so i am not able to think on how to apply lazy propagation there. could you help me out?
Best one
At 14:49, we have a condition about low>high but if mid = (low+high)/2, then why would ever the value of low be greater than high. The condition seems somewhat useless? Am I missing something?
You are right, low>high will always be false and you can remove the condition if you want.
That statement is a simple check at the last leaf node in the segment tree at (n-1,n-1) where the function COULD make a recursive call to its right side (we know this wont actually happen though) and therefore its just added in as a sanity check.
Although Tushar does mention while going through the code at 14:51 saying "at this point it doesn't happen" which is very misleading because it implies that there is a point where it could happen which we now know is not true. Cheers :P
thank you so much you are the best ^_^
at 24:42 , is there a way to not update element. when there is no overlap, it can save some time.
Please Enlighten me if i am wrong?
you are awesome...
hey i wanna ask if you got a video that explain the " balanced binary search tree "
which solve the proplem like if you got Q query and in each query you got
left and right and you must print the most Freq(the value that appears most) between
left and right inclusive
Thanks a lot.
how would lazy propagation change the complexity? on an average case, it should still take the same time, i think. can anyone explain this to me?
alright, Thanks!
if after incrementing from [0,0] to 2, we do the query to find minimum between [2,3] then according to your concept the answer should be 5 but the actual answer will be 1.
Please justify it. I am highly confused.
sarthak gupta Sorry.. I was wrong..got it
SegmentTree[pos] += (high-low+1)*Lazy[pos];
I have seen a C++ code of Lazy Propagtion where the above line has been used while updating the "pos"ition of the Segment Tree when the value at the same "pos"ition in the Lazy tree is non-zero. I have run that program with the same input and getting the desired answer. Can anyone tell the meaning of this line and why it has been not been used in the video?
thx!
can u please tell me what are startrange, endrange and low, high?
thanks in advance
what if, we were required to update ranges (and not know which element is minimum in that particular range) before printing the final array. How would the algorithm change then to get better optimization.
There is a huge array with all elements set to 0, initially. We are required to update portions of array (from some left index to right index) multiple times. If we choose to do it over loop (brute force it) complexity would be O(N square). How do we update it optimally? example
arr[10]={0};
update [2,7] by 1
update [4,10] by 2
update [3,4] by 3
and finally, print the array:
0 1 4 6 3 3 3 1 1 1
how can i do something like after update original array should also gets changed ...
any thoughts ?
Can you upload any video for persistent segment tree?
sir, can u plz explain the implicit treaps using split and merge functions.
can i get some examples ... links please
Please post some videos on how to approach the problems of Dynamic Programming
Why we need if(low > high) condition, there won't be such cases if a query is already low
exactly
What is low>high condition?
invalid condition
Awesome _ / \ _
Hello bro!...I am you, from the past, when you'll see this comment after 5-6 years✌️..
Just wanna say, everything will be alright bro. And you'll realise then, that the time right now was not that tough than you thought in your past
please talk slower