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.
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 :)
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.
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
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.
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.
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
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 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.
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)
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
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
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?
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?
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.
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 🤔🤔🤔
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!
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 :)
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.
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 !!!
Really man hats off to you..able to understand in one go!!
its quite good explanation of lazy propagation.....thanks ..
Your videos are awesome Sir!..Very much easier to understand than TopCoder tutorials!
Thanks, this is one of the best video tutorial of lazy propagation in youtube!
Thanks for great video Tushar. Your explanations are incredibly helpful !
Your explanation is pro level! It helped me so much to understand such a difficult concept.
Very informative channel Tushar. Feels great to realise (after seeing your LinkedIn) that you did your bachelors from MNNIT as well.
this all, 8 yrs ago.
gotta appreciate the 1080p res and the screen sharing at that time!
Excellent explanation. Thank you sir. You made actually a diffucult topic to an eaay one with your clear explanation
Thanks for the simple explanation, it helped me a lot!
Finally,lazy propagation! Your videos are the best thanks.
Bhaiyya video kaafi sahi tha... Especially wo effects
You are the man! Can;t have a better explanation than this.
Understood easily from this video. Can you also provide complexity analysis of these functions in the future videos? It would be very helpful
The only video I understood about LP
Hey Tushar! amazing work. you make people understand the concepts.
One request, can you please make a video on persistent segment tree?
Such an awesome explanation with examples.
Thanks man for this video..
Now i am able to solve the problems based on lazy propagation
Tushar really appreciate your work. Thank you!
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
It's still nice even it has been 4 years since the date the video was uploaded....
Your videos are really helpful..Thank you very much n keep up the good work...
thanks for the video, keep uploading new videos it helps very much...
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.
Awesome Video for any beginner in segment Trees !!! :)
Great explanation, and thanks very much for the code, it was very useful
Thank you sir....for making such a useful video....
the best tutorial by the best teacher thanks a lot :)
Thanks. Very useful and properly explained.
Thank you so much man, you are the best.
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.
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
Your videos are amazing..thanks a ton sir.
Looking forward to your update.
ABSOLUTELY RELIABLE
This dude is legend!!!!!
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.
Thanks man ! ...Awesome lectures !!
Awesome one!! thank you very much Sir.
lazy prop feels like a bureaucrat came up with a algorithm for seg tree
this tutorial is awesome！as the title segment tree made simple
is if(low>high) return necesasary? great video btw
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?
awesome Video.... and max here meant INFINITY right??
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!
Thankyou sir....The video helped me alot
Excellent Explanation!!
Awesome explanation
Thank you Tushar!!
Can we store the minimum index instead of the value and still use lazy propagation technique?
Nice Lecture.
Have you made any video on Binary Indexed Tree(BIT)?
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?
please add one video for " updating values in segment tree "
i think this itself is an example of updating segment tree
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?
Only one word! Amazing!
Great explanation....thanks
nice. finally i understood lazy :)
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
Thank you.....Great work.!!
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
fantastic! thanks a lot
you really, nailed it!!
Great lesson!
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!
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?
awsome explanation :)
thanks man ,you are great..
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?
Nice Posting! Thanks
You are Too good bro
Thank you so much !
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
Can you upload any video for persistent segment tree?
Thank you so much.
can u please tell me what are startrange, endrange and low, high?
thanks in advance
how can i do something like after update original array should also gets changed ...
any thoughts ?
Beautiful!
thank you so much you are the best ^_^
sir, can u plz explain the implicit treaps using split and merge functions.
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 🤔🤔🤔
good job!
Why we need if(low > high) condition, there won't be such cases if a query is already low
exactly
thank you so much
you are awesome...
Thanks a lot.
What is low>high condition?
invalid condition
It is very hard algoritim.
can i get some examples ... links please
Best one
Please post some videos on how to approach the problems of Dynamic Programming
thx!
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
Awesome _ / \ _
please talk slower