Lazy Propagation Segment Tree

Рет қаралды 94,357

Tushar Roy - Coding Made Simple

9 жыл бұрын

Update segment tree lazily.
/ tusharroy25
github.com/mission-peace/inte...
github.com/mission-peace/inte...

Пікірлер: 111

@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 8 жыл бұрын

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

@Sandeep-gv2qk 7 жыл бұрын

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

@tahanimachowdhury 8 жыл бұрын

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.

@tarunanand2455 8 жыл бұрын

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

@rishabhagarwal9871 8 жыл бұрын

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

@RaviRaj-zz3bt 7 жыл бұрын

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

@shantanukshire79 3 жыл бұрын

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

@jianpengyu9843 2 жыл бұрын

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

@sadagopanns6267 8 жыл бұрын

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

@varunsinghania3683 8 жыл бұрын

Tushar really appreciate your work. Thank you!

@ashishnegi9663 3 жыл бұрын

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

@vishalsheth1888 8 жыл бұрын

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

@chuka231d8 2 жыл бұрын

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

@shivangidhakad9807 8 жыл бұрын

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

@chennakeshavabs5294 6 жыл бұрын

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

@lostgen36 4 жыл бұрын

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

@sly_sloth 4 ай бұрын

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

@Sandeepg255 8 жыл бұрын

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

@rovsenhuseynov8368 Жыл бұрын

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

@himanshusagar115 8 жыл бұрын

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

@yadurajdeshmukh9032 4 жыл бұрын

Bhaiyya video kaafi sahi tha... Especially wo effects

@saidattathallam 8 жыл бұрын

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

@luanleonardo Жыл бұрын

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

@adityasingh5002 7 жыл бұрын

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

@tino96ptv 6 жыл бұрын

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

@shubhamk840 3 жыл бұрын

Such an awesome explanation with examples.

@mickyor1107 8 жыл бұрын

Thank you so much man, you are the best.

@nitinpaliwal9196 8 жыл бұрын

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

@swapnilgupta5707 3 жыл бұрын

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

@vikramadityakukreja4795 6 жыл бұрын

Thanks. Very useful and properly explained.

@devanshuLitoria 8 жыл бұрын

Your videos are amazing..thanks a ton sir.

@meganlee5897 6 жыл бұрын

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

@leightonchoi8644 7 жыл бұрын

Looking forward to your update.

@huynhquocthang5399 4 жыл бұрын

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

@adityakumarghosh433 8 жыл бұрын

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

@IshanSharma0019 8 жыл бұрын

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.

@ashish3192 7 жыл бұрын

Awesome one!! thank you very much Sir.

@dipankardey7917 7 жыл бұрын

Thanks man ! ...Awesome lectures !!

@SankalpAnand 8 жыл бұрын

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.

@Garentei 4 жыл бұрын

The only video I understood about LP

@angshumansarma2836 5 жыл бұрын

This dude is legend!!!!!

@rsgames12 8 жыл бұрын

Great explanation....thanks

@visheshsrivastav2107 6 жыл бұрын

Thankyou sir....The video helped me alot

@unfoldingcode 4 жыл бұрын

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

@GautamKumar-tn7ev 8 жыл бұрын

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

@jaymodi2037 7 жыл бұрын

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 4 жыл бұрын

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

@sarfarazalam6077 4 жыл бұрын

Thank you Tushar!!

@puneetkumar9609 7 жыл бұрын

Only one word! Amazing!

@shivshankarjha4818 7 жыл бұрын

Awesome explanation

@karannagpal2611 7 жыл бұрын

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?

@talalal-hamidi3093 8 жыл бұрын

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

@saifullahrahman 3 жыл бұрын

fantastic! thanks a lot

@PengLi53 8 жыл бұрын

Great lesson!

@kshitijagarwal3230 4 жыл бұрын

Excellent Explanation!!

@mehedimim3248 4 жыл бұрын

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

@RajMishra-mq5zm 3 жыл бұрын

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.

@mauriciojuarez9920 2 жыл бұрын

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

@atishnarlawar1177 6 жыл бұрын

Beautiful!

@genuineprofile6400 7 жыл бұрын

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

@sarwarjahan05 6 жыл бұрын

nice. finally i understood lazy :)

@shobhitsrivastava4496 4 жыл бұрын

you really, nailed it!!

@ravibansal1996 8 жыл бұрын

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 5 жыл бұрын

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!

@saumya1857 6 жыл бұрын

awsome explanation :)

@abdulquaumopu1126 8 жыл бұрын

Can you upload any video for persistent segment tree?

@roh9934 7 жыл бұрын

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?

@obitouchiha5082 2 жыл бұрын

Thank you so much !

@khoatruong9751 7 жыл бұрын

Nice Posting! Thanks

@rishabhthakur1031 8 жыл бұрын

thanks man ,you are great..

@nehapoonia8080 7 жыл бұрын

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

@offchan 8 жыл бұрын

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

@hope-jh7bv 3 жыл бұрын

Thank you so much.

@jdragon8184 3 жыл бұрын

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

@mail2shandilya 8 жыл бұрын

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 6 жыл бұрын

how your code screen was?

@agnibhachakz 6 жыл бұрын

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?

@sourabhjangid8013 5 жыл бұрын

You are Too good bro

@ZiadxKabakibi 8 жыл бұрын

thank you so much you are the best ^_^

@AbhaySingh-dm4zr 6 жыл бұрын

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

@PankajKumar-hp5gc 6 жыл бұрын

you are awesome...

@axehai 8 жыл бұрын

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 8 жыл бұрын

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 8 жыл бұрын

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

@the343totalitarian 6 жыл бұрын

Thanks a lot.

@gijoe4681 5 жыл бұрын

good job!

@vivekawasthi4625 8 жыл бұрын

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

@joydeepbhattacharjee3849 3 жыл бұрын

i think this itself is an example of updating segment tree

@puneetkumarsingh1484 3 жыл бұрын

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 3 жыл бұрын

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

@thefuntech2810 3 жыл бұрын

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

@promethuser 8 жыл бұрын

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 8 жыл бұрын

alright, Thanks!

@mujahidulislam315 4 жыл бұрын

Best one

@siddharthchabukswar2 6 жыл бұрын

can i get some examples ... links please

@ozgurkaragul9898 4 жыл бұрын

It is very hard algoritim.

@sarthakgupta7273 8 жыл бұрын

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 8 жыл бұрын

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

@vaibhavkhandelwal737 6 жыл бұрын

What is low>high condition?

@ApoorvaRajBhadani 3 жыл бұрын

invalid condition

@SHADOW5487 6 жыл бұрын

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

@deshanshgarg2778 5 жыл бұрын

exactly

@ashish3192 7 жыл бұрын

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

@akashjain4184 7 жыл бұрын

Awesome _ / \ _

@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