Binary Index Tree: Efficient Accumulative Sum or Count

There is a special data structure called Binary Indexed Tree that we can use to solve problems which need accumulative sum or counts efficiently which is based on the idea of storing the partial sums. We then use these partial sums to obtain the overall sum in the sumRegion method. The way we store these partial sums in a Binary Indexed Tree (BIT), a.k.a. Fenwick Tree, allows us to achieve both the update and query to be done in logarithmic time.

Consider the case of 1-D array. Assume we have an array nums of size 8 (nums[1], nums[2] ... nums[8]) (1-based indexing). We store the partial sums of the array nums in another array bit of size 8 (bit[1], bit[2] ... bit[8]). The idea is to compute each value of bit array in a way that allows us to "quickly" compute the sum as well as update the values for the array nums. We do it using the idea of bit manipulation.

Each number can be represented as sum of power of two’s and this is what will allow us to obtain the overall sum from the partial sums. For example, 7 can be represented as 1+2+4=(20+21+22)1 + 2 + 4 = (2^{0} + 2^{1} + 2^{2})1+2+4=(20+21+22) hence whenever we want to calculate the cumulative sum till 7th index in the nums array, we will utilize the values stored in the 1st, 2nd and 4th index in the bit array. Here in case of Binary Indexed Tree, the 1st, 2nd and 4th index of the bit array will store the non-overlapping partial sums which can be added up to obtain the cumulative sum till 7th index in the nums array. Hence, we have cum_sum(7)=bit[1]+bit[2]+bit[4]=a[1]+a[2]+...+a[7]cum\_sum(7) = bit[1] + bit[2] + bit[4] = a[1] + a[2] + ... + a[7]cum_sum(7)=bit[1]+bit[2]+bit[4]=a[1]+a[2]+...+a[7] (where cum_sum(7) refers to cumulative sum till 7th index of nums array). But how do we obtain the sum in such a manner? For this, consider the bit array as shown below (let's assume that we can efficiently obtain the below mentioned array, we'll discuss later how we can actually do it).

bit[1] = nums[1]
bit[2] = nums[1] + nums[2]
bit[3] = nums[3]
bit[4] = nums[1] + nums[2] + nums[3] + nums[4]
bit[5] = nums[5]
bit[6] = nums[5] + nums[6]
bit[7] = nums[7]
bit[8] = nums[1] + nums[2] + nums[3] + nums[4] + nums[5] + nums[6] + nums[7] + nums[8]

When we try to calculate cumulative sum till any index n the steps that we follow are.

1. Decompose n as the sum of power of 2’s. Let’s say n=n1+n2+…+nkn = n_{1} + n_{2} + … + n_{k}n=n1​+n2​+…+nk​ where each of the number nin_{i}ni​ is a number which is a power of 2. For example, When n=7n = 7n=7, we have n1=1,n2=2,n3=4 (7=1+2+4)n_{1} = 1, n_{2} = 2, n_{3} = 4\ (7 = 1 + 2 + 4)n1​=1,n2​=2,n3​=4 (7=1+2+4)
2. The cumulative sum till index n in the nums array can then be obtained with the help of bit array as cum_sum(n)=bit[n1]+bit[n2]+...+bit[nk]cum\_sum(n) = bit[n_{1}] + bit[n_{2}] + ... + bit[n_{k}]cum_sum(n)=bit[n1​]+bit[n2​]+...+bit[nk​]

As mentioned before, since we’ll store the values in the bit array as non-overlapping partial sums, that’s why step 2 is possible and gives us the cumulative sum as the sum of the values from the bit array. The question that we must ask now is - How can we build the bit array in such a manner? For this, we need to do two things.

1. Understand lsb (least significant bit, non-zero) of a number.
2. Observe the pattern of occurence of each number from nums array in the bit array.

LSB (least significant bit)

Consider the binary representation of 5 (5 -> 101). The least significant (non-zero) bit of a number is obtained by taking the right most non-zero bit from the binary representation and ignoring all the other bits (i.e. considering all the other bits as 0). Hence lsb(5) = 001 (considering only the rightmost non-zero bit and ignoring all others). Similarly lsb(6) = 010. Why? Since 6 -> 110 and the right most set bit occurs at the second position.

Next, let’s notice the occurence of each element of nums array in the bit array as follows.

nums[1] isPresentIn -> bit[1], bit[2], bit[4], bit[8]
nums[2] isPresentIn -> bit[2], bit[4], bit[8]
nums[3] isPresentIn -> bit[3], bit[4], bit[8]
nums[4] isPresentIn -> bit[4], bit[8]
nums[5] isPresentIn -> bit[5], bit[6], bit[8]
nums[6] isPresentIn -> bit[6], bit[8]
nums[7] isPresentIn -> bit[7], bit[8]
nums[8] isPresentIn -> bit[8]

Let’s convert all the indices shown above into their binary representation. We then have (indices for nums array on the LHS and bit array on the RHS)

LHS        -> RHS
nums[0001] -> bit[0001], bit[0010], bit[0100], bit[1000]
nums[0010] -> bit[0010], bit[0100], bit[1000]
nums[0011] -> bit[0011], bit[0100], bit[1000]
nums[0100] -> bit[0100], bit[1000],
nums[0101] -> bit[0101], bit[0110], bit[1000]
nums[0110] -> bit[0110], bit[1000]
nums[0111] -> bit[0111], bit[1000]
nums[1000] -> bit[1000]

On seeing the pattern above, we can notice that the sequence of indices on the RHS can be obtained by continuously adding the number to it’s lsb, starting from the index on the LHS.

Example

0101 -> (add 0001) -> 0110 -> (add 0010) -> 1000

We can use this observation to build the bit array as we now know all the indices in the bit array where a particular value from the nums array occurs.

Note: We have used 1-based indexing at all the places in the 1-D BIT explanation part.

The process of adding a particular number val to the appropriate locations in the bit array is what is known as the update process in a Binary Indexed Tree. Hence we can re-write the above code as.

int bit[];  // initialize all entries in bit array to 0
int nums[]; // given nums array
int n;      // size of nums array

int lsb(int n) {
    // the line below allows us to directly capture the right most non-zero bit of a number
    return n & (-n);
}

void updateBIT(int i, int val) {
    // keep adding lsb(i) to i and add val to bit[i]
    for (; i <= n; i += lsb(i)) {
        this->bit[i] += val;
    }
}

int buildBIT(int n) {
    for (int k = 1; k <= n; ++k) {
        int i = k, val = this->nums[k];
        updateBIT(i, val);
    }
}

As, we can see the code above that we are able to calculate sum and update or original nums while maintaining the accumulative sum both in O(log n). This approach can have applications in lots of real life applied problem and it is great tool to have in your arsenals.