Binary Indexed Trees

Tags: , , ,

Binary Indexed Trees (Fenwick Tree)

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 for segment 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 or Fenwick 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 index from 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 b¯  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.

int* construct_bit(int sum[], int length)
{
    int *tree = new int[length];
    tree[0] = 0;
    
    for(int idx = 1; idx < length; idx++)
    {
	int left, right;
	
	left = idx - (idx & (-idx));
	right = idx;

	tree[idx] = sum[right] - sum[left]; 
    }

    return tree;
}

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

int read_sum(int tree[], int index)
{
	int sum = 0;
	while(index > 0)
	{
		sum += tree[index];
		index -= (index & -index);
	}
	return sum;
}

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.

void update_tree(int idx, int val, int tree[])
{
	int length = sizeof(tree)/sizeof(int);
	idx++;
	while(idx <= length)
	{
		tree[idx] += val;
		idx += idx & (-idx);
	}
}

Binary Indexed Trees easy to code, the code length is very short and should be used wherever possible.
The Links of some practice problems are given below : 
http://www.spoj.com/problems/UPDATEIT/


http://www.spoj.com/problems/CTRICK/