Hacker News Reader

The Fenwick tree in your cheat sheet seems a little broken

Can you go into a little more detail? What is broken exactly?

The visual is extremely hard to understand how it relates to the description, given that it looks to be 1-indexed, but the description only makes sense for 0-indexing (4th element stores the sum of the first 4 elements), not to mention none of the binary indexes seem to be storing the correct sums (or they're storing sums of a tree that isn't being presented).

The visual is directly from here (I recommend you give it a read if you want to grasp the full intuition on how a Fenwick tree works (page 97)): https://cses.fi/book/book.pdf

I should have included the full visuals which are included there and I can see your point on why people would get confused by that visual - so I'll make a note to include the full image when I have more time. Thank you for the feedback.

Reply on news.ycombinator.com