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

This video explains, in the simplest way possible, a very frequently asked data structure which is segment tree in details with construction of segment tree along with operations like range sum query and update of old values to new value. CODE explanation is done after each operation for better understanding. CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...

[@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.

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

[@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

[@vikashmaddi1508]

Tech dose is underrated

[@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

[@lambar0]

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

[@techdose4u]

Thanks :)

[@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

[@bakrichodhpakistani7196]

best content on segment tree on ytube

[@techdose4u]

Thanks:)

[@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].

[@mondayemmanuel191]

You really know how to explain algorithms. Thank you.

[@techdose4u]

Welcome :)

[@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 😊

[@Pooja-xu4lp]

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

[@techdose4u]

Welcome :)

[@aaronpauljacob5143]

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

[@techdose4u]

Thanks

[@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.

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

[@high-oncode7576]

Support

[@techdose4u]

🔥

[@FWTteam]

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

[@techdose4u]

Nice :)

[@artistic__08]

Best explanation of segment tree indeed

[@choicespecss]

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

[@patienward]

You made it very clear to me! Thanks!

[@HimanshuKumar-xz5tk]

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

[@techdose4u]

👌🏼

[@shahperzia1121]

very Underrated channel bro, content quality is gold.

[@techdose4u]

Thanks

[@doitlikeprateek717]

The best channel for programming videos

[@robinofautumn99]

utterly smooth explanation!!😊😊

[@biswamohandwari6460]

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

[@techdose4u]

Nice :)

[@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.

[@harshdeepsinghful]

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

[@mohitbabani7816]

The explanation is very good, thank you so much🙏

[@techdose4u]

Welcome 🤗

[@bishalkumarnath3176]

Awesome Explanation. Couldn't be any better than this

[@techdose4u]

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.

[@leepakshiyadav1643]

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

[@namanmehra8097]

Really Clear Explaination

[@safalyaghoshroy2405]

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

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

[@akshatthakur5967]

excellent explanation

[@techdose4u]

Thanks :)

[@gauravkumarjaiswal8224]

Perfect explanation 😊

[@ksTales]

Sir no words to say how great you are

[@techdose4u]

❤️

[@vikashprasad1770]

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

[@techdose4u]

Welcome :)

[@manojamrutharaj9071]

Awesome explanation... Thanks...

[@mohitlaad8435]

great work! Thanks.

[@techdose4u]

Thanks :)

[@terigopula]

great video.. great explanation.. kudos :)

[@dollyakshaya7535]

great explanation bro

[@techdose4u]

Thanks :)

[@manngondaliya4704]

Bohot mast kaam karte hai aap .Keep it going

[@techdose4u]

Thanq bhai :)

[@ismail8973]

This class was really awesome

[@techdose4u]

Thanks

[@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?

[@rahulsaha7412]

You are always excellent, Sir

[@techdose4u]

Welcome

[@soumakpoddar4372]

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

[@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.

[@MarekXvX]

Great explanation! Thanks for your work!

[@dayanandraut5660]

Beautiful explanation 👌

[@techdose4u]

Thanks 😊

[@SahilKumar-yv8vh]

Thanks from IIT'K.

[@toekneema]

AMAZING, crystal clear!

[@techdose4u]

Thanks

[@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.

[@ryderdonahue]

Great explanation! Although I wish you covered the insert function

[@bhavnasoni9148]

Thank u for such a great explanation.

[@techdose4u]

Welcome :)

[@nikitabhalla524]

Just WoW

[@techdose4u]

Thanks :)

[@shubhammishra3012]

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

[@techdose4u]

Yes I will.

[@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?

[@cricsinghvlogz]

just wow !!

[@hereyoursdad]

very very nice

[@anshumansharma2251]

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

[@pawandeepsingh2155]

Awesome lecture

[@techdose4u]

Thanks :)

[@mohanawasthi7045]

Great sir

[@Mandeepsingh-jo5cf]

Thanks. correction: pink == purple;

[@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).

[@adityarathi3420]

Superb explanation ! Thanks a lot :-)

[@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?

[@manikantapunnam1189]

Thanks a lot

[@TheSridharraj]

Masssssss

[@techdose4u]

:)

[@Ishwarsingh-zq5ig]

thank you sir

[@ranitdey7369]

Excellent buddy. keep it up !

[@techdose4u]

Sure :)

[@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.

[@srinivasreddydanda1777]

awesome man. Thanks !!

[@techdose4u]

Welcome :)

[@rishabhmishra9611]

Well explained

[@techdose4u]

Thanks

[@adityasinghaswal4923]

best!

[@spetsnaz_2]

Good Explanation....

[@techdose4u]

Thanks :)

[@SreekantShenoy]

wow!

[@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.

[@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

[@Ali-mc4le]

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

[@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

[@najimali32]

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

[@HimanshuSingh-ob9qo]

👌👌👌👌👌🙏

[@jaydalsaniya6986]

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

[@jalsacentre1040]

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

[@kumarakash5219]

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

[@mwshubham]

Did you ever recieve negative comment on your videos?

[@techdose4u]

Only when I announced about paid LIVE course 😂

[@mwshubham]

@@techdose4u haha.

[@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

[@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.

[@nitya5120]

2*(si+1) hoga maybe

[@DogVideos-Tommy]

In update why we are not adding

[@DogVideos-Tommy]

when l==r

[@hillarioushollywood4267]

we are adding in right subtree

[@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.

[@ayushgarg5929]

Size kitna hoga array ka ?

[@techdose4u]

Heap jaise implement krte ho waise hi krna.

[@user-ls6qw2vw6i]

I still not understand

[@ojasvityagi9569]

GOLD

[@techdose4u]

:)

[@amitavamozumder73]

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

[@edward8111]

Leatcode 307

[@abhireddy8164]

Thank u sir

[@techdose4u]

Welcome :)