I think that the original paper by Fenwick is much clearer. The answer above by @templatetypedef requires some "very cool observations" about the indexing of a perfect binary tree, which are confusing to me.

Fenwick simply said that the responsibility range of every node in the interrogation tree would be according to its last set bit:

E.g. as the last set bit of 6==00110 is a "2-bit" it will be responsible for a range of 2 nodes. For 12==01100, it is a "4-bit", so it will be responsible for a range of 4 nodes.

So when querying F(12)==F(01100), we strip the bits one-by-one, getting F(9:12) + F(1:8). This is not nearly a rigorous proof, but I think that's it's more obvious when put so simply on the numbers axis and not on a perfect binary tree, what are the responsibilities of each node, and why is the query cost equals to the number of set bits.

If this is still unclear the paper is very recommended.

I think that the original paper by Fenwick is much clearer. The answer above by @templatetypedef requires some "very cool observations" about the indexing of a perfect binary tree, which are confusing and magical to me.

Fenwick simply said that the responsibility range of every node in the interrogation tree would be according to its last set bit:

E.g. as the last set bit of 6==00110 is a "2-bit" it will be responsible for a range of 2 nodes. For 12==01100, it is a "4-bit", so it will be responsible for a range of 4 nodes.

So when querying F(12)==F(01100), we strip the bits one-by-one, getting F(9:12) + F(1:8). This is not nearly a rigorous proof, but I think that's it's more obvious when put so simply on the numbers axis and not on a perfect binary tree, what are the responsibilities of each node, and why is the query cost equals to the number of set bits.

If this is still unclear the paper is very recommended.