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

แชร์
ฝัง
  • เผยแพร่เมื่อ 28 พ.ย. 2024

ความคิดเห็น • 168

  • @yushdecides
    @yushdecides 4 ปีที่แล้ว +42

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

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว +4

      Thanks bro :)

    • @kasecastiel5826
      @kasecastiel5826 3 ปีที่แล้ว

      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
      @emilioangelo4753 3 ปีที่แล้ว

      @Kase Castiel instablaster =)

    • @kasecastiel5826
      @kasecastiel5826 3 ปีที่แล้ว

      @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
      @kasecastiel5826 3 ปีที่แล้ว

      @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
    @AtulKumarVermaOnline 3 ปีที่แล้ว +10

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

  • @aishwaryadwani9365
    @aishwaryadwani9365 4 ปีที่แล้ว +3

    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 !

  • @martinharris4416
    @martinharris4416 3 ปีที่แล้ว +4

    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

  • @lambar0
    @lambar0 ปีที่แล้ว +3

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

  • @SR-we1vl
    @SR-we1vl 4 ปีที่แล้ว +19

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

  • @getsuha
    @getsuha 3 ปีที่แล้ว +1

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

  • @shubhammishra3012
    @shubhammishra3012 4 ปีที่แล้ว +11

    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

  • @bakrichodhpakistani7196
    @bakrichodhpakistani7196 3 ปีที่แล้ว +1

    best content on segment tree on ytube

  • @neerajkulkarni6506
    @neerajkulkarni6506 3 ปีที่แล้ว +2

    One of the best explanation of segment trees on TH-cam! Great video.

  • @vikashmaddi1508
    @vikashmaddi1508 3 ปีที่แล้ว +5

    Tech dose is underrated

  • @mondayemmanuel191
    @mondayemmanuel191 3 ปีที่แล้ว +7

    You really know how to explain algorithms. Thank you.

  • @Pooja-xu4lp
    @Pooja-xu4lp 3 ปีที่แล้ว +3

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

  • @pradiplamsal1403
    @pradiplamsal1403 ปีที่แล้ว

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

  • @mohammadtej5980
    @mohammadtej5980 3 ปีที่แล้ว +3

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

  • @doitlikeprateek717
    @doitlikeprateek717 2 ปีที่แล้ว

    The best channel for programming videos

  • @shahperzia1121
    @shahperzia1121 3 ปีที่แล้ว +1

    very Underrated channel bro, content quality is gold.

  • @ArjunArjun-zg3mz
    @ArjunArjun-zg3mz 3 ปีที่แล้ว +2

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

  • @FWTteam
    @FWTteam 4 ปีที่แล้ว +2

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

  • @high-oncode7576
    @high-oncode7576 3 ปีที่แล้ว +4

    Support

  • @artistic__08
    @artistic__08 10 หลายเดือนก่อน

    Best explanation of segment tree indeed

  • @aaronpauljacob5143
    @aaronpauljacob5143 4 ปีที่แล้ว +9

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

  • @HimanshuKumar-xz5tk
    @HimanshuKumar-xz5tk 3 ปีที่แล้ว +1

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

  • @choicespecss
    @choicespecss ปีที่แล้ว

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

  • @patienward
    @patienward ปีที่แล้ว

    You made it very clear to me! Thanks!

  • @biswamohandwari6460
    @biswamohandwari6460 4 ปีที่แล้ว +1

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

  • @leepakshiyadav1643
    @leepakshiyadav1643 2 ปีที่แล้ว

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

  • @robinofautumn99
    @robinofautumn99 8 หลายเดือนก่อน

    utterly smooth explanation!!😊😊

  • @bishalkumarnath3176
    @bishalkumarnath3176 3 ปีที่แล้ว +1

    Awesome Explanation. Couldn't be any better than this

  • @harshdeepsinghful
    @harshdeepsinghful 2 ปีที่แล้ว

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

  • @ksTales
    @ksTales 3 ปีที่แล้ว +1

    Sir no words to say how great you are

  • @techmind9608
    @techmind9608 4 ปีที่แล้ว +1

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

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว +1

      Keep watching :)

  • @mohitbabani7816
    @mohitbabani7816 3 ปีที่แล้ว +1

    The explanation is very good, thank you so much🙏

  • @safalyaghoshroy2405
    @safalyaghoshroy2405 4 ปีที่แล้ว

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

  • @namanmehra8097
    @namanmehra8097 3 ปีที่แล้ว

    Really Clear Explaination

  • @MarekXvX
    @MarekXvX 2 ปีที่แล้ว

    Great explanation! Thanks for your work!

  • @ismail8973
    @ismail8973 3 ปีที่แล้ว +1

    This class was really awesome

  • @manngondaliya4704
    @manngondaliya4704 4 ปีที่แล้ว +1

    Bohot mast kaam karte hai aap .Keep it going

  • @vikashprasad1770
    @vikashprasad1770 3 ปีที่แล้ว +1

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

  • @gauravkumarjaiswal8224
    @gauravkumarjaiswal8224 9 หลายเดือนก่อน

    Perfect explanation 😊

  • @rahulsaha7412
    @rahulsaha7412 4 ปีที่แล้ว +1

    You are always excellent, Sir

  • @dayanandraut5660
    @dayanandraut5660 3 ปีที่แล้ว +1

    Beautiful explanation 👌

  • @toekneema
    @toekneema 4 ปีที่แล้ว +1

    AMAZING, crystal clear!

  • @akshatthakur5967
    @akshatthakur5967 3 ปีที่แล้ว +1

    excellent explanation

  • @SahilKumar-yv8vh
    @SahilKumar-yv8vh 7 หลายเดือนก่อน

    Thanks from IIT'K.

  • @originaladmin
    @originaladmin 4 ปีที่แล้ว +1

    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
    @bhavnasoni9148 4 ปีที่แล้ว +1

    Thank u for such a great explanation.

  • @manojamrutharaj9071
    @manojamrutharaj9071 2 ปีที่แล้ว

    Awesome explanation... Thanks...

  • @terigopula
    @terigopula 2 ปีที่แล้ว

    great video.. great explanation.. kudos :)

  • @chiragchatwani9124
    @chiragchatwani9124 4 ปีที่แล้ว +5

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

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว

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

  • @mohitlaad8435
    @mohitlaad8435 ปีที่แล้ว +1

    great work! Thanks.

  • @dollyakshaya7535
    @dollyakshaya7535 ปีที่แล้ว +1

    great explanation bro

  • @adityarathi3420
    @adityarathi3420 3 ปีที่แล้ว

    Superb explanation ! Thanks a lot :-)

  • @pawandeepsingh2155
    @pawandeepsingh2155 4 ปีที่แล้ว +1

    Awesome lecture

  • @twishabansal263
    @twishabansal263 4 ปีที่แล้ว +1

    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
      @techdose4u  4 ปีที่แล้ว +1

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

  • @ranitdey7369
    @ranitdey7369 3 ปีที่แล้ว +1

    Excellent buddy. keep it up !

  • @ryderdonahue
    @ryderdonahue 2 ปีที่แล้ว

    Great explanation! Although I wish you covered the insert function

  • @AmanKumar-fd5ec
    @AmanKumar-fd5ec 4 ปีที่แล้ว

    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?

  • @mohammadyahya78
    @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?

  • @Mandeepsingh-jo5cf
    @Mandeepsingh-jo5cf 3 ปีที่แล้ว

    Thanks.
    correction: pink == purple;

  • @hereyoursdad
    @hereyoursdad 2 ปีที่แล้ว

    very very nice

  • @sezgingul6166
    @sezgingul6166 4 ปีที่แล้ว +2

    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
      @techdose4u  4 ปีที่แล้ว +1

      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
    @mohanawasthi7045 ปีที่แล้ว

    Great sir

  • @srinivasreddydanda1777
    @srinivasreddydanda1777 3 ปีที่แล้ว +1

    awesome man. Thanks !!

  • @rishabhmishra9611
    @rishabhmishra9611 4 ปีที่แล้ว +1

    Well explained

  • @shubhammishra3012
    @shubhammishra3012 4 ปีที่แล้ว +1

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

  • @manikantapunnam1189
    @manikantapunnam1189 3 ปีที่แล้ว

    Thanks a lot

  • @spetsnaz_2
    @spetsnaz_2 4 ปีที่แล้ว +1

    Good Explanation....

  • @soumakpoddar4372
    @soumakpoddar4372 3 ปีที่แล้ว +1

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

  • @nikitabhalla524
    @nikitabhalla524 3 ปีที่แล้ว +1

    Just WoW

  • @Ali-mc4le
    @Ali-mc4le 4 ปีที่แล้ว +1

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

  • @cricsinghvlogz
    @cricsinghvlogz 2 ปีที่แล้ว

    just wow !!

  • @abhireddy8164
    @abhireddy8164 4 ปีที่แล้ว +1

    Thank u sir

  • @Ajay-ju2ig
    @Ajay-ju2ig 4 ปีที่แล้ว +1

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

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว +1

      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.

  • @najimali32
    @najimali32 4 ปีที่แล้ว

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

  • @anshumansharma2251
    @anshumansharma2251 2 ปีที่แล้ว

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

  • @chetan_bommu
    @chetan_bommu 2 ปีที่แล้ว

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

  • @TheSridharraj
    @TheSridharraj 3 ปีที่แล้ว +1

    Masssssss

  • @adityasinghaswal4923
    @adityasinghaswal4923 2 ปีที่แล้ว

    best!

  • @jaydalsaniya6986
    @jaydalsaniya6986 2 ปีที่แล้ว

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

  • @SreekantShenoy
    @SreekantShenoy 2 ปีที่แล้ว

    wow!

  • @hillarioushollywood4267
    @hillarioushollywood4267 2 ปีที่แล้ว

    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?

  • @HimanshuSingh-ob9qo
    @HimanshuSingh-ob9qo 3 ปีที่แล้ว +1

    👌👌👌👌👌🙏

  • @somnathmukherjee4305
    @somnathmukherjee4305 4 ปีที่แล้ว +1

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

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว +1

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

    • @somnathmukherjee4305
      @somnathmukherjee4305 4 ปีที่แล้ว

      Okay

  • @jalsacentre1040
    @jalsacentre1040 3 ปีที่แล้ว +1

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

    • @kumarakash5219
      @kumarakash5219 3 ปีที่แล้ว

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

  • @kushwanthkapa2041
    @kushwanthkapa2041 3 ปีที่แล้ว

    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

  • @AlayDhagia
    @AlayDhagia 4 ปีที่แล้ว

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

    • @hillarioushollywood4267
      @hillarioushollywood4267 2 ปีที่แล้ว

      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

  • @roshan84ya99
    @roshan84ya99 4 ปีที่แล้ว +1

    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
      @techdose4u  4 ปีที่แล้ว +1

      Use Fenwick tree for easier implementation wherever possible.

  • @abhireddy8164
    @abhireddy8164 4 ปีที่แล้ว

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

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว

      Provide me the question link.

    • @abhireddy8164
      @abhireddy8164 4 ปีที่แล้ว

      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
      @abhireddy8164 4 ปีที่แล้ว

      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
      @techdose4u  4 ปีที่แล้ว

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

    • @abhireddy8164
      @abhireddy8164 4 ปีที่แล้ว

      Ok sir it's fine.

  • @nitya5120
    @nitya5120 3 ปีที่แล้ว

    2*(si+1) hoga maybe

  • @ojasvityagi9569
    @ojasvityagi9569 4 ปีที่แล้ว +1

    GOLD

  • @ayushgarg5929
    @ayushgarg5929 4 ปีที่แล้ว +1

    Size kitna hoga array ka ?

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว

      Heap jaise implement krte ho waise hi krna.

  • @mwshubham
    @mwshubham 3 ปีที่แล้ว +1

    Did you ever recieve negative comment on your videos?

    • @techdose4u
      @techdose4u  3 ปีที่แล้ว +1

      Only when I announced about paid LIVE course 😂

    • @mwshubham
      @mwshubham 3 ปีที่แล้ว

      @@techdose4u haha.

  • @amitavamozumder73
    @amitavamozumder73 3 ปีที่แล้ว

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

  • @sainathmandavilli6538
    @sainathmandavilli6538 3 ปีที่แล้ว +1

    i think update takes 0(n) in worst case

    • @hillarioushollywood4267
      @hillarioushollywood4267 2 ปีที่แล้ว

      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.

  • @DogVideos-Tommy
    @DogVideos-Tommy 3 ปีที่แล้ว

    In update why we are not adding

  • @edward8111
    @edward8111 ปีที่แล้ว

    Leatcode 307

  • @蓉张-b6x
    @蓉张-b6x 3 ปีที่แล้ว

    I still not understand

  • @Ishwarsingh-zq5ig
    @Ishwarsingh-zq5ig 2 ปีที่แล้ว

    thank you sir