Why do we add the least significant bit while updating some index in Fenwick trees?

Revision en2, by marlonbymendes, 2017-03-04 05:31:03

Several guides explain how Fenwick trees (BIT) work (and they do it pretty well), but I don't see any intuition or proof on it's correctness, specially the update operation. I've used BIT before and I know "how" it works, but not "why" the update operation works.

Here's the usual update code, taken from Topcoder's tutorial.

void update(int idx ,int val){
    while (idx <= MaxVal){
        tree[idx] += val;
        idx += (idx & -idx);
    }
}

Popular guides on BIT (don't actually answer the "why" question):

Topcoder

GeeksForGeeks

Tushar Roy's video

Also, pllk recent book, page 86. Link

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English marlonbymendes 2017-03-04 05:31:03 2 Tiny change: 'estion):\n[Topcode' -> 'estion):\n\n[Topcode'
en1 English marlonbymendes 2017-03-04 05:30:32 984 Initial revision (published)