Fenwick Trees: The Most Useful Data-Structure You've Never Heard Of | Hacker News Reader

Fenwick Trees: The Most Useful Data-Structure You've Never Heard Of

bugfix-66.com

3 pointsbugfix-663 comments

Question for you bugfix-66:

I'm struggling a bit with this one, having not previously encountered the Fenwick Tree concept.

Why isn't there a main which actually used the code? It'd help me trace through to better understand what the intended outcome is, especially if it's a failing test case.

Also, what is the purpose of this line?

    i += i & -i

Is this the line which clears the lowest bit?

Edit: one small feedback, when I submitted the form before making any edits, I saw a hint on the next page. Consider detecting the noop and hide the hint, instead prompting the user to "try something, anything!" or similar.

Keep up the good work! Your site is so cool.

n & -n is an old trick that gives a number with a single bit in it, the bottom bit that was set in n, the & operator takes precedence I believe.

I want the hint to be available easily.

  i += i & -i

adds the least-significant bit of i to i. This is not specific to Fenwick trees, it's a very common idiom.

Essentially, it doubles the size of the fragment to find the containing fragment. The addition can carry, for example 12+4 = 16 so the next larger fragment can be more than twice as large as the fragment we modified.

The idea is that these puzzles are very simple to fix. But you have to ponder the code (or research it elsewhere) to understand it enough to pinpoint the problem.

To fix the bug, simply change

  sum := 0

  sum := f.tree[0]

I think BUGFIX-66 may be too difficult for most people here on Hacker News. Even problem #1, which is almost trivial, is only solved by 2% of people who attempt it!

Reply on news.ycombinator.com