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):
