Update step in Fenwick Trees

Question

My question concerns the full reasoning behind the update step in Binary Indexed Trees (Fenwick Trees). As such, when updating our array with a certain increment, at a certain position, the update goes like this:

void updateBIT(int BITree[], int n, int index, int val)
{
    // index in BITree[] is 1 more than the index in arr[]
    index = index + 1;

    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
       // Add 'val' to current node of BI Tree
       BITree[index] += val;

       // Update index to that of parent in update View
       index += index & (-index);
    }

My problem is with the index += index & (-index); part. Please note that I understand the index & (-index) bit, especially in the context of querying the tree.

I've tried several examples by hand using this index update rule, but I haven't been able to find the logic behind adding index & (-index) in order to go to the next node that needs to be updated.

From what I got up until this point, a node i in a BIT is 'responsible' for the original values in the array ranging from [i - i & (-i) + 1, i], so that implies that any node would fall into a range of this form. Specifically, as I understand it, when wanting to update position k in the original array, we follow the following steps (conceptually, not in the actual code):

• Iteration 0: update BIT[k + 1] (indices are shifted by 1 in the BIT array) . While still at iteration 0, we update the index we're looking at, so I'd assume that we're looking for the next smallest interval that's responsible for node k, hence we need to find the next index i where i - i & (-i) < k < i. Find this index i by incrementing the current index by k & (-k).

The rest of the iterations occur in the same fashion until we go off limits. I've tried numerous examples by hand, and I still don't get why adding i & (-i) takes us to the right next node. Each and EVERY tutorial I found on the web, including videos, is completely dodgy on this matter.

There are several related questions about BITs here, please don't merge them with mine before reading it carefully. To my knowledge, this particular question has not been answered.

Answer 1

So, let me try to explain the above scenario by taking a simple example.

Let's take i = 12. Now we Update BIT[12]. Now next step according to the algorithm to update is i += i&(-i).

What is 12 in binary = 01100. The last bit set is 2, the value is 2^2 = 4 (as you know

0th bit value is 2^0 = 1
1st bit value is 2^1 = 2
2nd bit value is 2^2 = 4.

In similar fashion for other bits.

So now next index that we will update is 12 + 4 = 16. i.e BIT[16].

Now this was about how the system works. Let me try to explain in simple words why this technique works.

Let's Say I need to update index = 1 and let's say MAX array value is 8. So what all index I will update 1,2,4,8.

Now, let's say I need to update index = 3. So the array indexes will I update 3,4,8.

So you see how till now BIT[4] has got sum of all the values from array index 1 to 4.

Now suppose you need to get total sum for first 4 numbers, you just do BIT[4] and you will traverse through indexes 4,0. In short you don't traverse through 1,2,3. As we have seen how those indexes were covered because of bit manipulation.

Hope this helps!