Fenwick Tree range queries

Поділитися
Вставка
  • Опубліковано 24 сер 2024

КОМЕНТАРІ • 40

  • @boxxanon
    @boxxanon 5 років тому +52

    Best Fenwick Tree explanation currently on the internet... perhaps even the entire world. Congrats!

  • @cristian-adrianfrasineanu9855
    @cristian-adrianfrasineanu9855 2 роки тому +4

    i - LSB(i) is equivalent to i & (i - 1) to get the next greatest power of 2 that is smaller than i. This will save time with avoiding to write another function for parsing the bit representation of i.

    • @catte_6376
      @catte_6376 Рік тому

      it's actually `i & (-i)` !

  • @TheWildStatistician
    @TheWildStatistician 3 місяці тому +1

    Wow, just wow! On a side note, I think it's better to consider the position of the LSB in the 0-indexed way, since in that case an index is directly responsible for 2^(0-indexed position of LSB) element below it, inclusive of itself.
    Then cascading to the appropriate next element is intuitive, just remove the LSB. Essentially going down 2^(0-indexed position of LSB) :D.
    Anyways, fantastic job!

  • @user-ji9rn2mc6z
    @user-ji9rn2mc6z 6 років тому +14

    I FOUND IT!!! The best one! Thank you! :)

  • @harishvemula6709
    @harishvemula6709 5 років тому +2

    MASTER PIECE !! The best ever Fenwick tree tutorial on the universe .

  • @ThePabs213
    @ThePabs213 4 роки тому +3

    Awesome explanation, I would really appreciate a Segment Tree or Interval Tree explanation like this

  • @rishabhmishra9611
    @rishabhmishra9611 4 роки тому +1

    Really nice explanation everyone is just teaching how to code but is telling the fundamentals of this datastructures🔥

  • @eugnsp
    @eugnsp 6 років тому +2

    Bit manipulations are much easier and clearer if zero-based indexing is used rather than one-bases indexing. Then there is a direct correspondence between ranges of responsibilities and bit value in the n-th position.

    • @vipulgupta3827
      @vipulgupta3827 4 роки тому

      can you put more details related to 0 based indexing for this.
      i am not sure if 0 based indexing will work

  • @chiranjeevthomas4796
    @chiranjeevthomas4796 6 років тому +9

    Being a visual learner , these tutorials helped me to get the intuition behind the algorithm because of the visual aids you used . I revel in problem solving and am on codeforces and topcoder... I was really lacking in algo - ds knowledge and your tutorials are helping me up my game :D , thanks a lot bud .
    P.S - Please make a video on RANGE UPDATES too , that would really help !!

  • @user-vr9ok5uw1x
    @user-vr9ok5uw1x 4 роки тому

    I like your presentation and methodical approach.
    When material is shown properly It saves a lot of time.

  • @mathuratudu7271
    @mathuratudu7271 6 років тому +2

    The best video I ever watched on Fenwick Tree

  • @minghanxu7199
    @minghanxu7199 5 років тому +3

    I have to say this video is awesome and really clear! thanks!

  • @just_patricia280
    @just_patricia280 3 роки тому +1

    Thank you for the help! You rock!

  • @wanga6745
    @wanga6745 4 роки тому +1

    You are my hero, great explanation!

  • @abhinavsingh4221
    @abhinavsingh4221 4 роки тому +1

    This channel is awesome! Thank you buddy for your awesome videos :)

  • @karamkassem9821
    @karamkassem9821 5 годин тому

    Thanks for the explanation !
    But I can't see why this algorithm is good. Everyone is taking about how to get the ranges but no one is talking about how to build the tree, it will take O(nlogn) time which is not efficient !
    I mean if we used the first method where building the prefix sum array is in O(n) time and access in O(1) time, it is more efficient for range sum problem !
    Any thoughts?

  • @vetiarvind
    @vetiarvind 2 місяці тому

    Dude this rocks..

  • @harshitsharma7358
    @harshitsharma7358 Місяць тому

    great explanation

  • @al-hassanmohamed2339
    @al-hassanmohamed2339 10 місяців тому

    Thanks a lot to you ❤

  • @geogreenmanu
    @geogreenmanu 3 роки тому +2

    12 in binary 1100, then LSB is at third position ? How?
    The least significant bit is the right-most bit in a string, if the bit are order right to left, as done in this example.

    • @joseville
      @joseville 3 роки тому +2

      Yeah, some of the language used is imprecise. Instead of LSB, it should be "Least Significant One". And also in this video, "third position" means the 2^2 = 4's place.

  • @vipulgupta3827
    @vipulgupta3827 4 роки тому

    @WilliamFiset can you please add some videos for Segment tree. Your explanations are brilliant

  • @pavan7959
    @pavan7959 6 років тому +1

    Thankyou so much sir your videos helped me a lot.

  • @erithion
    @erithion 5 років тому

    Great explanation. Thanks!

  • @purushottam2010
    @purushottam2010 4 роки тому

    Please make a video on range updates!! I am not able to find a way to grasp it

  • @arijit_ad
    @arijit_ad 6 років тому

    Every nicely explained. Can you also explain segment tree?

  • @ZakariaBinAhmed
    @ZakariaBinAhmed Рік тому

    💚

  • @sgdfdsgs
    @sgdfdsgs 2 роки тому

    what an amazing channel

  • @nitishshingde9767
    @nitishshingde9767 6 років тому +1

    great tutorial!!!

  • @JynyChen
    @JynyChen Рік тому

    2:32 what is PLA?

  • @rasca0027
    @rasca0027 6 років тому +2

    I have a question. at 5:10, isn't LSB the right-most bit, which is 0?

    • @WilliamFiset-videos
      @WilliamFiset-videos  6 років тому

      Yep, you're correct. That's a mistake in the audio recording, the slides are still accurate and highlight the LSB.

    • @rasca0027
      @rasca0027 6 років тому

      Thank you!

    • @kgzcq
      @kgzcq 4 роки тому +2

      @@WilliamFiset-videos Hi, do you mean the "LSB that is 1" ? because by definition, LSB is always the right-most bit, and according to the video/slides, you seem to be referring to the least significant bit that is a 1.

    • @joseville
      @joseville 3 роки тому

      @@kgzcq This! Another good term for it could be "Least significant One"

  • @AtiyaAnjum
    @AtiyaAnjum Рік тому

    😀

  • @hoanganhtu9090
    @hoanganhtu9090 2 роки тому

    the link is broken

  • @georgetsiklauri
    @georgetsiklauri 4 роки тому

    Mate, you've got quite a lot of some very strange cracking noise in your videos.. sort of you're juggling with iron balls during recording this video.. it's very annoying.