Fenwick tree / Binary indexed tree update operation

Prerequisite: Basic knowledge of Fenwick tree

In this blog, I will try to discuss why we do i = i + (i &(-i)) to find the index of BIT array to update.

To update array value a[i], Fenwick tree updates all BIT nodes in which a[i] contributes. So, we starts from BIT[i] and then try to find next index, j > i of BIT array such that a[i] contributes in BIT[j] and J is minimum index among all possible index.
We know that, BIT[x] contains (a[x], a[x-1], a[x-2], … , a[x-lsb_value(x) + 1]). Here, lsb_value(x) = 2^{lowest_significant_set_bit_of_x}.

To ensure that BIT[j] contains a[i], following condition should be maintained :
1. j-i < lsb_value(j)
2. j is minimum among all possible
Lets find index j. Before that define lsb_pos(x) = position of lowest significant set bit of x.

Case 1: lsb_pos(j) < lsb_pos(i)

At first, find the distance (j — i)

We know, if y > x and we take first T most significant bits from both i and j then (value of j for those t bits) > (value of i for those t bits).
lets, dis_1 = contribution of first T bit in distance. So, we can define distance :

Is this distance maintain the condition we find earlier ?

But, minimum value of dis_1 is 0. So, this case is not possible.

Case 2: lsb_pos(j) == lsb_pos(i)

Here, for first T bits, dis_1 can be minimum 1. Because, all bits after that are same for both i and j. But we know j > i.

But, distance is greater than 2^{lsb_pos(j)}. So, this condition is also not possible.

Case 3: lsb_pos(j) > lsb_pos(i)

Here, to ensure that j is minimum possible one, we can take most significant bits of j in first box same as i. So, lets ignore that part. Now, lsb_pos(y)-th bit of i should be 0 to ensure that j > i.

So, we can take any value in yellow part. Because, j−i<lsb_value(j) will be always maintained no matter what value we take in yellow part. Now, to find minimum possible J or minimum value of j-i , all the bits in yellow part should be 1.

That means j−i = lsb_value(i). So, we can say minimum value of j is :