Best articles to explain Binary Indexed Trees

Binary Indexed Trees (Fenwick Tree)

from: http://algorithmsandme.in/2015/02/binary-indexed-trees/

Why Binary Indexed Tree?

Consider an array A : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}, you have to find the sum of a range say (1,5). One way of doing this can be by keeping the sum of elements from index 0 to index i, where 0 <= i<= n. So the array with all the cumulative sum is “sum” :{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136} and to calculate sum from 1 to 5 we can simply do sum[5] – sum[1]. This will take O(n) precomputing time and O(q) with q queries with O(1) complexity per query.

Let us modify the question now, Suppose we have another query that modifies value at some index i,  this will make us calculate the sum from index ‘i’ to ‘n’ again. Now the complexity will be O(q*n) if there are ‘q’ queries. Segment trees can be used to solve this in O(q*log(n)). (Refer to this post forsegment trees).

Coding for segment trees can be a very lengthy and Hectic process, Segment Trees require a very large memory space, Debugging a code of segment tree is very difficult. Another approach to solve the above problem is to use Binary Indexed Tree data structure, which also has O(q*log(n)) complexity but BIT (Binary Indexed Trees) are much easier to code and require very less memory space than segment trees.
Binary Indexed trees are also called Fenwick Trees.

Representation of Binary Indexed Tree

Consider an input array A : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}. Binary Indexed Tree orFenwick tree is represented using an array of size n, where n is the length of the input array. Let’s call the binary indexed tree of this array “tree[n]”. tree[idx] (where idx is some index of BIT) will store the sum of values of the given input array from index (idx – 2^r +1)  to index idx. Here, r is the position of the last set bit (from left to right) in binary representation of the index idx

So, for example idx = 6, binary representation of 6 is 0110, Therefore the last set bit from left to right is the 1st bit (considering 0 based index) which makes r = 1. Therefore tree[6] stores the sum from index 5 to index 6.

The diagram below shows value of r for every indexfrom 1 to 16. The color of rth index is changed for better understanding.

Binary Indexed Tree

Therefore, tree[12] = A[9] + A[10] + A[11] + A[12]. To calculate “tree[idx]”, we can store the cumulative sum from index “0” to index “idx”  where (0 <= idx < n) in an array and then subtract “sum[idx – 2^r + 1]” from “sum[idx]”. This will find value of tree[idx] in O(1).

So, tree[idx] = sum[idx] – sum[idx – 2^r + 1]. 

How to Find the value of the last set bit?

Let num be an integer whose last set bit we want to isolate. Note that num can be represented in the form a1b, where a represents the series of bits before last set bit and b represents all the zeros after the last set bit.

Integer (-num) can be found out using 2’s complement of num, which is done by adding 1 to the inverse of num. the expression for finding twos complement is as follows,

(a1b)¯ + 1 = a¯0b¯ + 1
Since b consists of all zeroes, so consists all ones.
Therefore, finally we have
-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = a¯0(1…1) + 1 = a¯1(0…0) = a¯1b

Now, we can easily isolate the last digit, using bitwise operator AND with num and -num
a 1 b
&   a¯1 b
——————–
= (0…0)1(0…0)
So, to calculate the value of (idx – 2^r + 1) we just have to do the following operation

idx = idx – (idx & -idx);
Construction of Binary Indexed Tree
For every index “idx”, tree[idx] is calculated in O(1) complexity using the expression tree[idx] = sum[idx] – sum[idx – 2^r + 1], where “sum[idx]”stores the cumulative sum from index “0” to index “idx”.
The code is shown below.

 

Sum Between Two Indices

To calculate sum between two given indices l and r. We will have to calculate sum from index ‘0’ to index ‘r’, then the same thing from index ‘0’ to index ‘l’ and then calculate the difference between of the results obtained.

Let us consider an example of index 13, to calculate sum from index 0 to index 13, array tree will play a major role here, we know that tree[13] will store sum of 13th index only, tree[12] stores sum from 9th index to 12th index and tree[8] stores sum from  index 0 to index 8. So, adding tree[8] + tree[12] + tree[13] will give us cumulative sum from index 0 to index 13.
tree[13] = tree[13] + tree[12] + tree[8]
tree[1101] = tree[1101] + tree[1100] + tree[1000](Binary representation)

Note that, complexity of our algorithm to calculate sum from index 0 to index idx will be O(log(idx))
The diagram below illustrate this.

Binary Indexed Tree

The Code to find sum from index 0 to index idx is shown below

 
 

Update Value at some position and update BIT

If a value at some index idx is added by some value say val, then we will have to update the tree at all those places which are affected by this index. 
For example, if value at 9 is changed, then tree[10], tree[12], tree[16] …so on, will be changed because
tree[10] = tree[9] + tree[10];
tree[12] = tree[9] + tree[10] + tree[11] + tree[12];

while we were reading the sum, we were removing last set bit from index until it became zero. Now, while updating the tree we should add one set bit to the index idx until it becomes greater than or equal to length.

Below is the code to do that.

 

Binary Indexed Trees easy to code, code length is very short and should be used wherever possible.

Please suggest good articles in the comments.