Binary Indexed Tree ( Fenwick Tree) -Understanding the concept

BINARY INDEXED TREE (Fenwick tree)

MOTIVATION

Let us consider an array arr[0 . . . n-1]. With following two task to perform :- 

1.       Find the sum of first i elements.

2.      Change value of a specified element of the array arr[i] = x where 0 <= i <= n-1.

·         A simple solution is to run a loop from 0 to i-1 and calculate sum of elements. To update a value, simply do arr[i] = x. The first operation takes O(n) time and second operation takes O(1) time.

·         Or, Create another array and store sum from start to i at the i’th index in this array. Sum of a given range can now be calculated in O(1) time, but update operation takes O(n) time now.

Now the question arises can we perform both operation in O(log n) time ?

One can think about  segment tree but implementation using segment tree can be complex and require more memory.so better solution can be produced using binary indexed tree.

Complexities:

·         Time complexity of construction O(nlogn).

·         Time complexity of sum and update operation is O(logn).

·         Space complexity is O(n).

Representation

Binary Indexed Tree is represented as an array. Let the array be BITree[]. Each node of Binary Indexed Tree stores sum of some elements of given array. Size of Binary Indexed Tree is equal to n where n is size of input array. In the below code, we have used size as n+1 for ease of implementation (where 0^th indexed is used as a dummy node).initialized all the element of BITree[]={0}.

Operations

1.      Sum(index) : Returns sum of arr[0..index]

2.      update(index, val): Updates BIT for operation arr[index] += val

Algorithms

1.     Sum(index)

1.1.    Initialize sum as 0 and index as index+1.

1.2.    while index is greater than zero .

1.2.1.   Add BITree[index] to sum

1.2.2.    Go to parent of BITree[index].  Parent can be obtained by removing

       the last set bit from index, i.e., index = index - (index & (-index))

1.3.    Return sum

2.      Update(index, val)

       2.1.   Initialize index as index+1.

       2.2.   while index is smaller than or equal to n.

    2.2.1.            Add value to BITree[index]

    2.2.2.            Go to parent of BITree[index].  Parent can be obtained

                 by adding the decimal value of last set bit from index, 

                 i.e., index = index + (index & (-index))

[Note above formula adds decimal value corresponding to last set bit]