Sum of given range | Segment tree construction and update | Simplest explanation

[@yushdecides]

Whenever I want an explanation of any tough topic, I see your videos. They are just awesome.

[@techdose4u]

Thanks bro :)

[@kasecastiel5826]

i guess im asking the wrong place but does someone know of a tool to log back into an instagram account?? I somehow lost my account password. I would appreciate any tricks you can offer me

[@emilioangelo4753]

@Kase Castiel instablaster =)

[@kasecastiel5826]

@Emilio Angelo i really appreciate your reply. I got to the site through google and I'm in the hacking process atm. Looks like it's gonna take quite some time so I will get back to you later with my results.

[@kasecastiel5826]

@Emilio Angelo It did the trick and I now got access to my account again. I am so happy:D Thank you so much, you saved my ass !

[@AtulKumarVermaOnline]

Only a handful of KZbin channel explain the concepts in this much clarity and yours is definitely one of them. Keep going.

[@martinharris4416]

before seeing this video i feared segment trees as i used to hear this word when CP was mentioned but i never though someone would explain so beautifully

[@aishwaryadwani9365]

I was going through segment tree topic and saw your video. Now i don't have to watch/search for another videos. Thanks a ton !

[@techdose4u]

Welcome

[@SR-we1vl]

I guess in Efficient approach 01:24 Sum(L, R) should be Sum(L, R) = Sum[R] - Sum[L-1] ! Great Tutorial by the way! Thank you very much!!

[@techdose4u]

Welcome :)

[@lambar0]

Most Intuitive and comprehensive explanation so far…… I had watched three earlier videos on the topic giving scattered information….great job

[@techdose4u]

Thanks :)

[@shubhammishra3012]

I saw some of your lecture about rolling hash ,and this one , Your content is really worthy for competitive programming as well as interview purpose

[@techdose4u]

Thanks

[@Pooja-xu4lp]

On this topic, this is the best video. You saved my days and weeks. Thank you

[@techdose4u]

Welcome :)

[@mondayemmanuel191]

You really know how to explain algorithms. Thank you.

[@techdose4u]

Welcome :)

[@neerajkulkarni6506]

One of the best explanation of segment trees on KZbin! Great video.

[@techdose4u]

Thanks :)

[@pradiplamsal1403]

Such a clean explanation. Anybody with a Computer Science background would understand. Thank you very much.

[@getsuha]

Concise and compact. Only correction required at t=12.26, the two left most nodes have range [0-0] & [1-1] instead of [1-1] & [2-2].

[@high-oncode7576]

Support

[@techdose4u]

🔥

[@mohammadtej5980]

Best explanation of Segment tree, I understood it, thanks for your help. PS: I don't understand why people don't like such videos🤔

[@techdose4u]

Thanks 😊

[@ArjunArjun-zg3mz]

Really love the way you explain these concepts with pseudo code and examples you solve!!! It greatly help grasp the concept.

[@techdose4u]

Welcome :)

[@shahperzia1121]

very Underrated channel bro, content quality is gold.

[@techdose4u]

Thanks

[@vikashmaddi1508]

Tech dose is underrated

[@FWTteam]

I searched a lot and my search ended here. Superb explaination 🔥

[@techdose4u]

Nice :)

[@HimanshuKumar-xz5tk]

I love this way of making video, everything explained from basic with comparison of different approaches.

[@techdose4u]

👌🏼

[@bakrichodhpakistani7196]

best content on segment tree on ytube

[@techdose4u]

Thanks:)

[@aaronpauljacob5143]

🔥 🔥 🔥 Such amazing explanation!!! 🔥 🔥 🔥 You are a wonderful teacher sir. The video was so simple to understand and exactly what was needed. ⭐️ ⭐️ ⭐️

[@techdose4u]

Thanks

[@doitlikeprateek717]

The best channel for programming videos

[@biswamohandwari6460]

Mind blowing explanation understand every word in the video best one ever

[@techdose4u]

Nice :)

[@leepakshiyadav1643]

I was scared of this topic, you made it damn simple and fun to understand, thanks a ton :)

[@choicespecss]

This was the best explanation of segment trees I've seen! Subscribed and Liked

[@harshdeepsinghful]

Well the topic was explained so well, felt like segment tree is such a easy topic

[@techmind9608]

dude ,,seriously what do u eat,,,,this video deserve more views,,,,,best ever video i hv seen:),,,i am addicted to ur channel :),,,

[@techdose4u]

Keep watching :)

[@mohitbabani7816]

The explanation is very good, thank you so much🙏

[@techdose4u]

Welcome 🤗

[@ksTales]

Sir no words to say how great you are

[@techdose4u]

❤️

[@bishalkumarnath3176]

Awesome Explanation. Couldn't be any better than this

[@techdose4u]

Thanks :)

[@artistic__08]

Best explanation of segment tree indeed

[@robinofautumn99]

utterly smooth explanation!!😊😊

[@patienward]

You made it very clear to me! Thanks!

[@safalyaghoshroy2405]

Sir your process of explaining problems is excellent and video is superb. Pls add more videos of fenwick tree. Thank you.

[@manngondaliya4704]

Bohot mast kaam karte hai aap .Keep it going

[@techdose4u]

Thanq bhai :)

[@ismail8973]

This class was really awesome

[@techdose4u]

Thanks

[@vikashprasad1770]

Very well explained sir, thanks a lot for this !!!

[@techdose4u]

Welcome :)

[@namanmehra8097]

Really Clear Explaination

[@MarekXvX]

Great explanation! Thanks for your work!

[@dayanandraut5660]

Beautiful explanation 👌

[@techdose4u]

Thanks 😊

[@rahulsaha7412]

You are always excellent, Sir

[@techdose4u]

Welcome

[@chiragchatwani9124]

you will have a Million subs one day. thank you so much can you explain Quick select algorithm

[@techdose4u]

I already did explain quick select (even though using OK too many times :P ). Check it once.

[@gauravkumarjaiswal8224]

Perfect explanation 😊

[@akshatthakur5967]

excellent explanation

[@techdose4u]

Thanks :)

[@terigopula]

great video.. great explanation.. kudos :)

[@toekneema]

AMAZING, crystal clear!

[@techdose4u]

Thanks

[@manojamrutharaj9071]

Awesome explanation... Thanks...

[@originaladmin]

Hi. Very nice explanation. One thing though. I think the size of the tree should be pow(2, h +1) - 1, not pow(2, h) - 1.

[@bhavnasoni9148]

Thank u for such a great explanation.

[@techdose4u]

Welcome :)

[@mohitlaad8435]

great work! Thanks.

[@techdose4u]

Thanks :)

[@dollyakshaya7535]

great explanation bro

[@techdose4u]

Thanks :)

[@ranitdey7369]

Excellent buddy. keep it up !

[@techdose4u]

Sure :)

[@ryderdonahue]

Great explanation! Although I wish you covered the insert function

[@adityarathi3420]

Superb explanation ! Thanks a lot :-)

[@pawandeepsingh2155]

Awesome lecture

[@techdose4u]

Thanks :)

[@SahilKumar-yv8vh]

Thanks from IIT'K.

[@twishabansal263]

Great one. Just a suggestion though: It would be better if the written code is typed or something. That's easier to understand than the hand writing.

[@techdose4u]

I did not use to include code explanation earlier but now I have been doing it.

[@mohammadyahya78]

Thank you very much. At 1:05 you said we need O(n.q) to find sum, do you mean by q = n^2 so O(n^3)? Because we need 3 loops in the bruteforce approach. I am I wrong please?

[@shubhammishra3012]

Please make the videos for heaps,heap sort and Fenvick Tree ,that will be really helpful

[@techdose4u]

Yes I will.

[@srinivasreddydanda1777]

awesome man. Thanks !!

[@techdose4u]

Welcome :)

[@sezgingul6166]

Very good explanation ! I have a question though, at 3:11min you say "we use segment trees when we have more updates..." you meant the opposite right?

[@techdose4u]

No. If you don't have updates then simply use array otherwise if updates are needed then use segment tree instead of array. Use lazy propagation to get more efficiency.

[@mohanawasthi7045]

Great sir

[@rishabhmishra9611]

Well explained

[@techdose4u]

Thanks

[@hereyoursdad]

very very nice

[@nikitabhalla524]

Just WoW

[@techdose4u]

Thanks :)

[@Ajay-ju2ig]

We use array for storing value in segment tree .It is possible some index in middle of the array is empty?

[@techdose4u]

If it is a Full binary tree then No. Gaps will only be at the end.Leaf nodes will be storing the actual array elements. Internal nodes will have range query values.

[@AlayDhagia]

At 2:10 Wont the TC for range sum queries be O(Q logN) ?

[@hillarioushollywood4267]

Yes it would definitely be O(QlogN) if there are Q queries, but in this video he is talking about only 1 query so logN

[@anshumansharma2251]

insertion and deletion in bst (segment tree) takes O(logn) time so how it is O(q) and O(n) in sum?

[@soumakpoddar4372]

I think the size of the segment tree should be 2*(2^h-)1.....Correct me if I am wrong

[@somnathmukherjee4305]

Can u please make a video on MO's algorithm too as very less resources are there in KZbin??

[@techdose4u]

Yea I understand. I will add it to list but it won't be possible with leetcode daily challenges.

[@somnathmukherjee4305]

Okay

[@manikantapunnam1189]

Thanks a lot

[@Mandeepsingh-jo5cf]

Thanks. correction: pink == purple;

[@cricsinghvlogz]

just wow !!

[@Ali-mc4le]

Hi Sir, what tool are you using to draw and write your solutions?

[@spetsnaz_2]

Good Explanation....

[@techdose4u]

Thanks :)

[@chetan_bommu]

For array, Shouldn't Q query time be O(N + Q)? which can be said as O(N). As we first create the array and then do Q operations in O(Q).

[@najimali32]

If nums are negative then diff should be mod of new value minus previous one ??

[@AmanKumar-fd5ec]

Really Awesome and Simplest way to understand this important and tricky data structure. By the way which software do you use for the demonstration which gives a black background?

[@hillarioushollywood4267]

How come the time complexity of udaption is O(LogN), it should be O(N) as you are still updating each and every node in right sub segment tree. Even in the worst case where updation index is 1, then definitely it is O(N). Can you please explan @techDose?

[@jalsacentre1040]

1:27 it should be num[R]-sum[L-1]

[@kumarakash5219]

You are right ...i have same doubt bro..

[@abhireddy8164]

Thank u sir

[@techdose4u]

Welcome :)

[@TheSridharraj]

Masssssss

[@techdose4u]

:)

[@jaydalsaniya6986]

A minor change in the formula. It should be , sum ( L , R ) = sum [ R ] - sum [ L-1 ] .

[@roshan84ya99]

Why we are using segment tree still we need to calculate or go for the node till we did not find the value total overlapping 🙄

[@techdose4u]

Use Fenwick tree for easier implementation wherever possible.

[@adityasinghaswal4923]

best!

[@nitya5120]

2*(si+1) hoga maybe

[@kushwanthkapa2041]

sir i think it is not full binary tree because in full binary tree leaf nodes are only present at last level..................... in 5:16

[@abhireddy8164]

Longest substring containing vowels in even counts.please add to the queue sir

[@techdose4u]

Provide me the question link.

[@abhireddy8164]

There is no question link in gfg too sir.but similar questions are minimum window string.it might uses sliding window protocol or it might use dynamic programming.actually I see that question in amazon interview experience in gfg.

[@abhireddy8164]

Given a string print the largest sub-string containing vowels in even counts.O(n) eg. S-> aqwrteakjeaghev , answer->aqwrteakje as it contain 2 ‘a’ and 2 ‘e’. Second in same question he want me to print all sub-string if multiple sub-strings are possible of same length.

[@techdose4u]

Okay... But if there is no question link then it is difficult to verify code and technique. Only intuition can be discussed.

[@abhireddy8164]

Ok sir it's fine.

[@HimanshuSingh-ob9qo]

👌👌👌👌👌🙏

[@ayushgarg5929]

Size kitna hoga array ka ?

[@techdose4u]

Heap jaise implement krte ho waise hi krna.

[@SreekantShenoy]

wow!

[@DogVideos-Tommy]

In update why we are not adding

[@DogVideos-Tommy]

when l==r

[@hillarioushollywood4267]

we are adding in right subtree

[@amitavamozumder73]

when you finally learn dp and found this where dp would be a bad solution :/

[@sainathmandavilli6538]

i think update takes 0(n) in worst case

[@hillarioushollywood4267]

Exactly, this is what I was looking for in the comments. Moreover, he is udapting every other element in right sub segment tree, so how come time complexity come out to be O(logN)? it is nearly O(N). More precisely, he is updating N/2 nodes.

[@mwshubham]

Did you ever recieve negative comment on your videos?

[@techdose4u]

Only when I announced about paid LIVE course 😂

[@mwshubham]

@@techdose4u haha.

[@ojasvityagi9569]

GOLD

[@techdose4u]

:)

[@蓉张-b6x]

I still not understand

[@edward8111]

Leatcode 307

[@Ishwarsingh-zq5ig]

thank you sir