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.
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!
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.
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 !!
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?
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.
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.
@@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.
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.
Best Fenwick Tree explanation currently on the internet... perhaps even the entire world. Congrats!
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.
it's actually `i & (-i)` !
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!
I FOUND IT!!! The best one! Thank you! :)
MASTER PIECE !! The best ever Fenwick tree tutorial on the universe .
Awesome explanation, I would really appreciate a Segment Tree or Interval Tree explanation like this
Really nice explanation everyone is just teaching how to code but is telling the fundamentals of this datastructures🔥
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.
can you put more details related to 0 based indexing for this.
i am not sure if 0 based indexing will work
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 !!
I like your presentation and methodical approach.
When material is shown properly It saves a lot of time.
The best video I ever watched on Fenwick Tree
I have to say this video is awesome and really clear! thanks!
Thank you for the help! You rock!
You are my hero, great explanation!
This channel is awesome! Thank you buddy for your awesome videos :)
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?
Dude this rocks..
great explanation
Thanks a lot to you ❤
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.
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.
@WilliamFiset can you please add some videos for Segment tree. Your explanations are brilliant
Thankyou so much sir your videos helped me a lot.
Great explanation. Thanks!
Please make a video on range updates!! I am not able to find a way to grasp it
Every nicely explained. Can you also explain segment tree?
💚
what an amazing channel
great tutorial!!!
2:32 what is PLA?
I have a question. at 5:10, isn't LSB the right-most bit, which is 0?
Yep, you're correct. That's a mistake in the audio recording, the slides are still accurate and highlight the LSB.
Thank you!
@@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.
@@kgzcq This! Another good term for it could be "Least significant One"
😀
the link is broken
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.