Fenwick Tree (Binary Index Tree) - Quick Tutorial and Source Code Explanation

[@antongeorgiev1089]

Just read 3 articles without understanding what a Fenwick Tree was, and then I came here. Good work!

[@stablesort]

Glad to hear that this video was helpful!

[@rahulchaubey8988]

Best explaination on FT so far i have seen..

[@stablesort]

Thanks for the compliment! By the way, I am looking for a subject for the next video. So if you have any suggestions, please do let me know. Thanks!

[@AshwaniYadavIIT]

@@stablesort how about FFT algorithm to compute coefficients of polynomial p3 (where p3 = p1*p2; p1, p2, p3 are polinomials)

[@stablesort]

@@AshwaniYadavIIT Thanks for an interesting suggestion! It's only been 20 years since I did anything with Fast Fourier transform =) I am adding it to my list. Cheers!

[@neyyars]

@@stablesort It would be great if you could explain an algorithm to settle that account among n number of friends, given an array indicating the amount each person will receive (+) or has to give (-) to settle the account. I am not aware of any greedy algorithms to solve this

[@stablesort]

@@neyyars Thanks for this suggestion. I'll add it to my list. Cheers!

[@theRenjie]

Every video of this guy is incredible... not sure how much time you have been putting into this work, kudos to you.

[@stablesort]

Thanks for the encouragement, Renjie! Sometimes I do think that I am putting way too much time into these videos. But reading your comments feels like an adrenaline shot that keeps me going =)

[@AbhishekVaid]

This is the best explanation of this concept anywhere on the internet. Amazing work.

[@eug_gino]

jesus christ, you are a very gifted teacher.

[@stablesort]

WOW, thanks! I hope my other videos can live up to your expectations =)

[@lambar0]

Clear and concise intuition building with splitting array

[@variksigurdsson1447]

This man is saving me in Algorithms right now, goodspeed

[@prakharnigam9757]

Your huge amount of effort that you put into these beautifully concise and crystal clear videos pays off by saving valuable time of thousands of students that learn from these super well made videos far greater than any other videos on KZbin!! I hope this gem of a channel never stops producing such high quality content.

[@stablesort]

Thank you for leaving such a wonderful compliment!

[@JuranHuang]

Every second of this 9 mins video is worth watching. You sir really are a talented teacher, showing the source code makes the concept so much easier to comprehend.

[@jimhuertascanaza2744]

sir u dont know how much this video help me, appreciate it

[@stablesort]

glad to hear it!!!

[@stretch8390]

You are a fantastic educator. If you've ever watched competitive programming streams where they explain the answers you'll know being good at something and being able to explain something are two very different things. You have done the community quite a service in bringing such clear explanations!

[@jehdawg]

Your videos are some of the best on KZbin. Incredibly clear and such interesting algorithms. I love how you explain the simple version of an algorithm before explaining the final version, makes things so clear!

[@stablesort]

Thank you for such a wonderful compliment!

[@Effulgence13]

This is the best Computer Science KZbin channel I’ve come across. Thank you for addressing difficult concepts in a calm, easy to understand, and friendly manner.

[@stablesort]

Wow, thank you for such a warm compliment!

[@OckeDFreestyler]

This is such a good explanation, thank you!

[@Morek000]

The best explanation on BIT I have ever seen!! Note at 4:07, the index 14 should be 15 - "2" = 13 rather than "1".

[@stablesort]

Yeap, well noted - thanks for keeping me honest!

[@chanyaoc]

There’s so many videos on computer algorithms on the internet these days, but hardly any could match up to the caliber of your videos. I am not sure how you manage to make these high-quality videos continuously but I am very thankful you do and kudos to you from Taiwan!

[@stablesort]

Hello from Los Angeles, and thank you for the kind words!

[@ragas1999]

You made is so simple to understand and write and recollect when needed

[@stablesort]

Thanks!

[@neyyars]

Very clear and concise. I was struggling to wrap my arms around this algorithm until I watched this video. Thank you so much!

[@stablesort]

Thank for leaving a compliment! Glad to hear that it made sense =)

[@MukulJainx]

This is the only video that explains how the Fenwick tree came into existence and why we have to travel with 2's complement, Thankyou!!

[@stablesort]

Thanks for the good words!

[@aries3690]

This video is so incredible!! This is the most clear explanation of Fenwick Tree Ive seen so far! Thank you so much for this

[@nicholaswei5307]

Great video! Much better than those hour long video loaded with ads. Thank you!

[@stablesort]

You are very welcome!

[@SanjaySinghaniaIN]

You are phenomenal. Your understanding of DS is remarkably deep and experienced! Much appreciation for sharing your painstakingly made absolutely lucid videos!! May God Bless You!!!

[@asdasdsal487]

Your explanation was amazing. Your narration and animation made it soo much easier to understand than other videos on this topic. I'm thankful for your efforts.

[@gabrielxu2087]

Amazing. The best tutorial for BIT

[@stablesort]

Thanks for the compliment!

[@kristopherbullinger213]

Excellent diagrams and animations. Thank you!

[@aiviskri]

That's the best explanation of Fenwick tree I've found on the internet

[@stablesort]

Thank you, I do appreciate your good words.

[@sing_tsang]

The only source that can help me understand BIT in 10 minutes.

[@stablesort]

glad to hear it!

[@changningli4107]

I love this guy's video. Great work. Look forward to your next episode.

[@SHUBHAMJHA-o3g]

Best explanation of fenvik tree I have seen

[@yangweiyili2514]

I can't be more thankful that I found this best ever video! Precise and concise, elegant!

[@stablesort]

Wow, thank you! Glad to hear that it was helpful!

[@Simranjotsinghwalia]

You explained the difficult concept so crisply and intuitively sir. Thank you 🙏

[@stablesort]

You are very welcome! Thanks for leaving such a wonderful compliment!

[@guitarbalaji]

I have watched 30-40 min long videos trying to explain BIT - I didn't get the intuition until I watched this 9 min video! Kudos :) Looking forward to more material...

[@stablesort]

Awesome, thank you! That was also my original motivation for making the tutorial - could not find one out there and so decided to make my own =)

[@suryavaliveti8355]

Thanks for the clear, concise and calm explanation. Your calmness makes it so much easier to learn :)

[@stablesort]

Thank you, that's a very nice compliment, I do appreciate it. I'll do my best to keep it up. By the way, after publishing each video, I start looking for a new topic to cover. So if you have any suggestions, please do let me know. Thanks!

[@suryavaliveti8355]

@@stablesort thank you. I am still new to data structures and algorithms so I will definitely let you know as I come across more stuff.

[@ciachn]

Awesome video! I had never heard of Fenwick trees, but now I know even how to implement one. Thanks!

[@FinLogan]

Nicely done! Was reading a book on this and was having a hard time understanding the authors, thanks for this clear explanation

[@anusatyachoudhary7171]

Excellent introduction of Fenwick Tree. Thanks Mr. Violentyev

[@stablesort]

You are very welcome and thanks for the compliment!

[@mridularao6449]

Such perfect explanation! just WOW!

[@elliegu274]

Insanely clear. Best explanation ever!

[@stablesort]

Cheers!

[@vali8924]

Finally i understand how a binary indexed tree works.Thank you

[@stablesort]

Glad it helped!

[@aliaksandrhn1]

Your diagram that starts at 3:01 explains it really clearly, much better than any tree-like depiction. I also liked your observation regarding the correlation between the rightmost bit set and the range that the given array cell covers. Additionally, while loop runs as many times as there are 1 bits in a binary representation of a number - also a great observation. A quality video and a great explanation, thank you, my Russian friend! Upvoted.

[@stablesort]

Thank you for leaving such a detailed account of what you liked about the video! This is useful feedback for me; I do appreciate it. Cheers!

[@gezhi9420]

This is the best video on BIT. The visualization is truly amazing.

[@stablesort]

Thanks for the compliment!

[@himachal8252]

The way you are explaining man, your channel is gonna be huge, keep up the good work 👍🏻

[@stablesort]

I do appreciate your vote of confidence!

[@EmadGohari]

Very clear explanation and awesome illustration! thank you!!

[@stablesort]

You are very welcome! Thanks for leaving a good word!

[@purplebunny6962]

You're the best, I'm learning so much about trees from your channel!!!

[@stablesort]

Glad to hear it!

[@evangelosrigas6985]

Thanks for the tutorial, a good accent, drawings & calm voice helps a lot in these videos, keep it up.

[@stablesort]

Hehe, chuckling about the accent comment :)

[@evangelosrigas6985]

@@stablesort HOLY, the video is 2y old and you replied in 1h lol, thats the first time thats happened to me, also, lol

[@MrAvadha1]

hey Andre, this video on Fenwick Tree is one of the most insightful videos I have seen on KZbin on DSA. The explanation and the supporting visualization is incredibly intuitive. I keep coming back to this video to refresh my understanding on Fenwick Tree. Really appreciate the efforts you have taken to polish the visualization part (through PPT I felt). Please do continue teaching DSA like the way you do. Your channel will soar like the bar graph in you profile pic :)

[@ijaz2020]

This is an excellent video. Subscribed immediately. Please post videos regularly.

[@stablesort]

Thanks for the words of encouragement! This kind of feedback really does motivate me to put time and effort into making new videos. By the way, I posted a new one just now (kzbin.info/www/bejne/pXK1kHiPmZ2co5I). That one is more of a brain teaser/coding problem but it builds on the information from this video. I hope you like.

[@qcqe]

thanks for helping me gain an appreciation for this structure

[@yamaan93]

I just wanted to say, this is an extremely well made video and helped me a lot. Thank you

[@tingwen524]

The best video of Fenwick tree I've seen so far! Thx a lot !!!!

[@stablesort]

My pleasure! Thanks for the compliment!

[@shivamjaiswal2742]

Damn..best explanation on YT

[@nabidulalam6956]

excellent, clear, concise explanation. subbed!

[@stablesort]

Thanks for the good words

[@evgenyfedorenko953]

Awesome video. Did not know we can populate Fenwick tree in linear time

[@hj2931]

nice video, thanks for sharing knowledge

[@maridavies3425]

Nice tutorial of a complex topic!

[@stablesort]

Thanks! More interesting episodes come out soon!

[@70da24]

First time on this channel, AND I LOVE IT! Thank you ,sir.

[@AnilabhaBaral]

Really a good explanation of Fenwick Tree in a very short time, kudos to you.

[@stablesort]

Glad it was helpful!

[@subhasreepatro7073]

Very nicely explained!

[@nhk_kakin_futuremvrcreator]

Good explanation, thank you.

[@stablesort]

Thanks for the compliment! Cheers!

[@mielewis3893]

This video is really helpful! Such a clear explanation of a difficult topic!

[@stablesort]

Thanks for the words of encouragement! I came across a few videos explaining Fenwick Trees that had good bits and pieces here and there. But none (that I could find) had a short and intuitive explanation from start to finish. Hence I made this video. Thanks for watching!

[@aryankhare9393]

Thank you for helping me visualise it

[@stablesort]

I am glad to hear that it helped!

[@ВоробійВіталій]

Great explanation, thank you!

[@amalroy7543]

Excellent.The best i could find for FT.Hope to see more videos from you on other topics as well.You really deserve more views.

[@stablesort]

Thanks a lot! More to come!

[@SeyhunSaryldz]

Thank you so much for your efforts. As usual, your explanation is the best one so far imo.

[@stablesort]

Thanks for the good words, I do appreciate it 😊

[@itsahandle]

This man is making ASMR for programmers

[@Ov3rdoseX]

Great stuff man - I rarely comment, but really have to tip my hat off to you. Thanks for putting all the effort in - it makes a difference :)

[@stablesort]

Glad to hear it! Thanks for the compliment!

[@nikitapodshivalov3573]

Thank you! It is a very detailed and good animated video

[@u2blr]

This is so easy to understand.. Thank you so much!

[@stablesort]

Thanks! Glad to hear that it made sense :)

[@izebit]

Thanks for the clear and short explanation. Please keep making videos, you are good at that 👏

[@stablesort]

Thanks, will do!

[@pangning3163]

Thank you so much for the clear explanation.

[@erikviking471]

Your fan club is growing hombre...

[@genghisda236]

Wao !! this channel only makes quality content. Awesome , why is there even 1 dislike in this video. These are some of the best explained videos on youtube.

[@stablesort]

Thanks! 😊

[@Nartymer]

WAHHHH! YOU HAVE NO IDEA HOW MUCH YOU HELPED MAN! I qualified for the national olympics of informatics in my country and binary index trees are often used to solve the given problems. It's the one piece of syllabus that I didn't quite understand. You helped me out immensely with this video, thank you!

[@stablesort]

WOW, good luck at the info olympics!

[@joshyatharva]

Thank you for this video! It's really short and very informative. Waiting for more!

[@stablesort]

Thanks, more videos are in the making! By the way, if you are interested in Fenwick Tree data structure, you may also enjoy this video on Segment Trees: kzbin.info/www/bejne/rqvXhmqioql_rJo Cheers, and let me know which other topics you'd like me to cover!

[@elmoad2055]

the best explanation ever thank you

[@stablesort]

Glad it was helpful!

[@007sya]

Very nice explanation! Good job

[@RishinderRana]

Amazing content! This concept is now rooted in my brain and thanks to you.

[@goncharivan]

Thank you, Andre!

[@stablesort]

You are very welcome, Ivan!

[@marciodojr]

Very good explanation, thank you very much!

[@ullas2101]

wow, great animations and to the point explanation. LOVE IT!!

[@stablesort]

Glad you liked it!

[@compraker]

Nicely explained!

[@stablesort]

Thanks! I am glad you liked it.

[@chinmayingle423]

You are underrated man, thanks for the awesome tutorial :)

[@stablesort]

Thanks for the compliment!

[@chinmayingle423]

@@stablesort :)

[@akashbhadouria6727]

Thanks a lot,love from India.

[@stablesort]

You are very welcome!

[@jwils1214]

Great video, thank you!

[@stablesort]

I am glad to hear that you liked it!

[@jwils1214]

​@@stablesort Sharing how to make the tree in linear time was helpful 😊

[@faizKhan-uv2dl]

Educational question: (Love the video, just curiosity) Although this video has less views, likes and comments than other related fenwick tree videos but somehow searching "fenwick tree" this is on top of the search list. How does youtube algorithm knows that this is the best video on this subject? Apart from basic things like, engagement on this video, the right keywords etc how do they find out? Did they watch it as well?

[@stablesort]

Haha, good question. I doubt they watch more than a small fraction of the videos themselves. I also do not think they care about keywords and such. My guess is that they do "AB testing" and keep track of what people do after having seen the video. For example, is someone searches for "fenwick tree", watches the first video but then stops half way through and watches the next, that tells the algorithm that the 1st video wasn't all that great. This is all speculation, of course. The exact methodology is a guarded secret =)

[@faizKhan-uv2dl]

​@@stablesort thats a good explanation. But isn't clicking the like button a proof that they found the video useful? Betting against that number must have alot of good reasons.

[@stablesort]

@@faizKhan-uv2dl Right, right, clicking the Like button and especially subscribing are probably major indicators. I was just thinking of other ways of extracting information from views that didn't result in Like button click. Hey, if you know more on the subject, do let me know =)

[@faizKhan-uv2dl]

@@stablesort i appreciate sharing your thoughts. I wouldn't know either, just thinking out loud.

[@Xeeto]

great video, thank you very much for the help.

[@stablesort]

You are very welcome; I am glad you like it!

[@rupjitchakraborty8012]

This is soooooo gooooood, please make more videos on advanced DS

[@stablesort]

Thanks, will do! By the way, any specific requests?

[@rupjitchakraborty8012]

@@stablesort Thanks for asking. Suffix Arrays and Trees, Segment Trees and Tries.

[@stablesort]

@@rupjitchakraborty8012 Cool, those are good suggestions. Adding to my to-do list. Thanks!

[@geck1204]

Omg this data structure has been so mysterious to me, but your explanation really helped. Thank you so much for this video!!!

[@charlesqwu]

Great video! Very clear explanation! By the way, when you say "last set bit", it is a bit ambiguous -- that is, you would need to clarify or define what you mean by "first" or "last" beforehand; maybe, "least significant set bit" or "right-most set bit" is less ambiguous.

[@g1ld]

Great explanation, thanks

[@stablesort]

Glad it was helpful!

[@areej5732]

Great video!

[@stablesort]

Thanks for the compliment!

[@GubenkovED]

masterfully done! 👏

[@shourabhpayal1198]

This channel is amazing

[@stablesort]

Thanks for the compliment!

[@nischaljain8140]

Highly grateful for such a wonderful explanation _/\_

[@harishtiet]

To reset the right most set bit can we also use N = N & (N-1) ?

[@wilsonemmanuel1352]

Exactly. and i prefer this one to his approach.

[@sachinfulsunge9977]

Very well Done!!

[@siddharthmagadum16]

best visualization 🔥

[@angkhoavo6305]

the video is very helpful anh fun , thanks for the video

[@simonvutov7575]

Great video man!

[@akshithreddyt89]

Please make more videos. I like them 😁

[@stablesort]

OK! And please do let me know if you have a topic for a video in mind. Cheers!

[@akshithreddyt89]

Please make a video on insert and delete in a complete binary tree. Thanks

[@stablesort]

@@akshithreddyt89 ​ Thanks for the suggestion! I am making a list of topics and I'll add your request to the list. Thanks again.