Lazy Propagation Segment Tree

[@ngc35ster]

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.

[@The_Promised_Neverland...]

people come and go, but their contribution remains... this channel proves it... Literally even after so many years, his vids still helping people

[@mattiamarchese6316]

The whole italian community of the IOI used this video to learn Segment Trees.

[@danielyeh2984]

This video enables me to fully understand the concept of Lazy Propagation. Thank you!

[@RaviRaj-zz3bt]

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 :)

[@rishabhagarwal9871]

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 !!!

[@tahanimachowdhury]

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.

[@Sandeep-gv2qk]

This is the best explanation of lazy propagation on the internet! Thanks mahn, keep up the good work!

[@tarunanand2455]

Really man hats off to you..able to understand in one go!!

[@sadagopanns6267]

Your videos are awesome Sir!..Very much easier to understand than TopCoder tutorials!

[@swapnilgupta5707]

its quite good explanation of lazy propagation.....thanks ..

[@jianpengyu9843]

Your explanation is pro level! It helped me so much to understand such a difficult concept.

[@ashishnegi9663]

Very informative channel Tushar. Feels great to realise (after seeing your LinkedIn) that you did your bachelors from MNNIT as well.

[@chuka231d8]

Thanks, this is one of the best video tutorial of lazy propagation in youtube!

[@shantanukshire79]

Thanks for great video Tushar. Your explanations are incredibly helpful !

[@sly_sloth]

this all, 8 yrs ago. gotta appreciate the 1080p res and the screen sharing at that time!

[@rovsenhuseynov8368]

Excellent explanation. Thank you sir. You made actually a diffucult topic to an eaay one with your clear explanation

[@yadurajdeshmukh9032]

Bhaiyya video kaafi sahi tha... Especially wo effects

[@Garentei]

The only video I understood about LP

[@lostgen36]

You are the man! Can;t have a better explanation than this.

[@luanleonardo]

Thanks for the simple explanation, it helped me a lot!

[@vishalsheth1888]

Finally,lazy propagation! Your videos are the best thanks.

[@himanshusagar115]

Thanks man for this video.. Now i am able to solve the problems based on lazy propagation

[@chennakeshavabs5294]

Understood easily from this video. Can you also provide complexity analysis of these functions in the future videos? It would be very helpful

[@shubhamk840]

Such an awesome explanation with examples.

[@shivangidhakad9807]

Hey Tushar! amazing work. you make people understand the concepts. One request, can you please make a video on persistent segment tree?

[@RajMishra-mq5zm]

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.

[@angshumansarma2836]

This dude is legend!!!!!

[@BojP4]

ABSOLUTELY RELIABLE

[@huynhquocthang5399]

It's still nice even it has been 4 years since the date the video was uploaded....

[@unfoldingcode]

Thank you sir....for making such a useful video....

[@varunsinghania3683]

Tushar really appreciate your work. Thank you!

[@mickyor1107]

Thank you so much man, you are the best.

[@adityakumarghosh433]

Awesome Video for any beginner in segment Trees !!! :)

[@saidattathallam]

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

[@Sandeepg255]

Your videos are really helpful..Thank you very much n keep up the good work...

[@vikramadityakukreja4795]

Thanks. Very useful and properly explained.

[@nitinpaliwal9196]

the best tutorial by the best teacher thanks a lot :)

[@leightonchoi8644]

Looking forward to your update.

[@adityasingh5002]

thanks for the video, keep uploading new videos it helps very much...

[@tino96ptv]

Great explanation, and thanks very much for the code, it was very useful

[@IshanSharma0019]

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.

[@shivshankarjha4818]

Awesome explanation

[@kshitijagarwal3230]

Excellent Explanation!!

[@dipankardey7917]

Thanks man ! ...Awesome lectures !!

[@mehedimim3248]

Thank you.....Great work.!!

[@sarfarazalam6077]

Thank you Tushar!!

[@devanshuLitoria]

Your videos are amazing..thanks a ton sir.

[@puneetkumar9609]

Only one word! Amazing!

[@ashish3192]

Awesome one!! thank you very much Sir.

[@meganlee5897]

this tutorial is awesome！as the title segment tree made simple

[@saifullahrahman]

fantastic! thanks a lot

[@obitouchiha5082]

Thank you so much !

[@hope-jh7bv]

Thank you so much.

[@rsgames12]

Great explanation....thanks

[@sarwarjahan05]

nice. finally i understood lazy :)

[@PengLi53]

Great lesson!

[@SankalpAnand]

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.

[@rishabhthakur1031]

thanks man ,you are great..

[@shobhitsrivastava4496]

you really, nailed it!!

[@roh9934]

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?

[@visheshsrivastav2107]

Thankyou sir....The video helped me alot

[@jdragon8184]

lazy prop feels like a bureaucrat came up with a algorithm for seg tree

[@puneetkumarsingh1484]

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?

[@wowtime7390]

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

[@ravibansal1996]

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.

[@BharatKumaryrBtech]

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!

[@vivekawasthi4625]

please add one video for " updating values in segment tree "

[@joydeepbhattacharjee3849]

i think this itself is an example of updating segment tree

[@saumya1857]

awsome explanation :)

[@offchan]

Can we store the minimum index instead of the value and still use lazy propagation technique?

[@mauriciojuarez9920]

is if(low>high) return necesasary? great video btw

[@khoatruong9751]

Nice Posting! Thanks

[@sourabhjangid8013]

You are Too good bro

[@talalal-hamidi3093]

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

[@agnibhachakz]

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?

[@RafaelSimarmata]

thank you so much

[@jaymodi2037]

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)

[@nikhilpandey3486]

I want to know how much your coding improved in these three years?

[@GautamKumar-tn7ev]

Nice Lecture. Have you made any video on Binary Indexed Tree(BIT)?

[@firefox-zzz]

thank you so much you are the best ^_^

[@abdulquaumopu1126]

Can you upload any video for persistent segment tree?

[@axehai]

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.

[@axehai]

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

[@vipulsharma1897]

can u please tell me what are startrange, endrange and low, high? thanks in advance

[@AbhaySingh-dm4zr]

how can i do something like after update original array should also gets changed ... any thoughts ?

[@atishnarlawar1177]

Beautiful!

[@nehapoonia8080]

sir, can u plz explain the implicit treaps using split and merge functions.

[@ozgurkaragul9898]

It is very hard algoritim.

[@promethuser]

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?

[@promethuser]

alright, Thanks!

[@the343totalitarian]

Thanks a lot.

[@gijoe4681]

good job!

[@genuineprofile6400]

awesome Video.... and max here meant INFINITY right??

[@PankajKumar-hp5gc]

you are awesome...

[@TheUnknownExplorerr]

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?

[@siddharthchabukswar2]

can i get some examples ... links please

[@mail2shandilya]

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.

[@SHADOW5487]

how your code screen was?

[@mujahidulislam315]

Best one

[@sarthakgupta7273]

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.

[@sarthakgupta7273]

sarthak gupta Sorry.. I was wrong..got it

[@thefuntech2810]

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 🤔🤔🤔

[@vaibhavkhandelwal737]

What is low>high condition?

[@ApoorvaRajBhadani]

invalid condition

[@hoyinli7462]

thx!

[@ashish3192]

Please post some videos on how to approach the problems of Dynamic Programming

[@SHADOW5487]

Why we need if(low > high) condition, there won't be such cases if a query is already low

[@deshanshgarg2778]

exactly

[@depression_plusplus6120]

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

[@akashjain4184]

Awesome _ / \ _

[@Quang1498]

please talk slower