Algotree > Algorithms > Binary Indexed Tree / Fenwick Tree

Binary Indexed Tree / Fenwick Tree

BIT ( Binary Indexed Tree ) / Fenwick Tree
Binary Indexed Tree ( a.k.a Fenwick Tree ) is a data structure represented using an array. Binary Indexed Tree is used to perform the below operations in logarithmic [ O ( log N ) ] time. – Finding out the prefix sum of the elements in the array. – Doing range sum queries. i.e Range_Sum ( l … r ) = A_l + A_l+1 + A_l+2 + … + A_r – Updating the element at a given index in the array.

BIT ( Binary Indexed Tree ) / Fenwick Tree

Binary Indexed Tree ( a.k.a Fenwick Tree ) is a data structure represented using an array.
Binary Indexed Tree is used to perform the below operations in logarithmic [ O ( log N ) ] time.
    – Finding out the prefix sum of the elements in the array.
    – Doing range sum queries. i.e Range_Sum ( l … r ) = A_l + A_l+1 + A_l+2 + … + A_r
    – Updating the element at a given index in the array.

If we use a precomputed prefix sum array for answering the prefix sum or the range sum queries, it would still take O ( N ) time if there are updates to the array elements in between answering the queries.

Below is an example of constructing a Binary Indexed Tree from an array.

– Calculate the range sum of lengths 2⁰ till 2 ^{log₂ ( N )} starting from index 1 covering the array length.
Example : We find the range sum beginning with index 1 as below ( for logical level 0 ) and continue to fill the range sum for all the unfilled incides ( for logical levels below ).

Start index	Range Size	Range	Range Sum
1	2⁰	1 … 1	4
1	2¹	1 … 2	-1
1	2²	1 … 4	7
1	2³	1 … 8	15

Note : We cannot go beyond the range size 2³ as 2⁴ = 16 which is more than the length of the array.

Binary_Indexed_Tree_Range_Sum

Finding the prefix sum of elements in the array using BIT

We use the Binary Indexed Tree for answering the prefix sum queries in O ( log N ) time.

Example : Consider finding the sum of first 14 numbers in the array. To find the sum, we start with index 14 in the BIT and traverse all the way up to the root in the tree. As we traverse up the tree, we add the content of each node to find the sum.

To find the parent of a node, we toggle the last set bit of the node.

Index ( current node )	Binary	BIT [Index]	Sum	To find the next index ( parent node )
14	[ 1 1 1 0 ]	2	2	Unset the last set bit ( 14 ) [ 1 1 1 0 ] -> ( 12 ) [ 1 1 0 0 ]
12	[ 1 1 0 0 ]	6	8 ( 2 + 6 )	Unset the last set bit ( 12 ) [ 1 1 0 0 ] -> ( 8 ) [ 1 0 0 0 ]
8	[ 1 0 0 0 ]	15	23 ( 8 + 15 )	Unset the last set bit ( 8 ) [ 1 0 0 0 ] -> ( 0 ) [ 0 0 0 0 ]

Binary_Indexed_Tree_Range

In the example we see that the prefix sum ( 1…14 ) can be queried in 0 ( log₂ N ) time. Binary_Indexed_Tree_Range

Thus, for finding the range sum, we make use of the below algorithm.

Algorithm Sum ( index )
   Initialize sum = 0
   While ( index > 0 ) {
         sum += bit [ index ]
         Toggle the last set bit to find the next index.
         index = index - ( index & ( -index ) )
   }
   return sum
}

Updating the original array and BIT

If the original array is updated by adding an element to a specific index, then we also update the BIT. The update operation take O ( log N ) time.

Example : Consider updating the element at index position 5 in the array. We perform add operation to update the element.
ADD ( index, delta ). i.e ADD ( 5, 2 ).
We update the BIT by adding 2 to all the ranges of which the index 5 is part of.
From the BIT we see that index 5 is part of the ranges [ 1…8 ], [ 5…5 ] and [ 5…6 ].

To update all the indices that are part of ranges [ 1…8 ], [ 5…5 ] and [ 5…6 ] we start from index 5 and traverse upwards.

To find the parent of a node, we add 1 to the last bit of the current node.

Binary_Indexed_Tree_Range

Thus, for updating the array used for storing the BIT, we make use of the below algorithm.

Algorithm Add ( index, delta )
   While ( index < size of BIT ) {
         bit [ index ] += delta
         # To add 1 to the last set bit do the below
         index = index + ( index & ( -index ) )
   }

Binary Index Tree implementation

from typing import List

class BIT :

    def __init__ (self, arr : List[int]) :
        # The number of nodes in a binary indexed tree 
        # is 1 more than the elements in the array
        self.bit = [0] * (len(arr) + 1) # list to store the binary indexed tree
        for i in range (len(arr)) :
            # Create the binary indexed tree array (bit) from the array elements
            # We fill the binary indexed from index 1
            self.Add (i+1, arr[i])

    # Find the sum of elements from the beginning upto right.
    def Sum (self, index : int) -> int :
        _sum = 0
        while (index > 0) :
            _sum += self.bit[index]
            index = index - (index & (-index))
        return _sum

    # Find the sum of array elements from left upto right.
    def Range_Sum (self, left : int, right : int) -> int :
        return self.Sum (right + 1) - self. Sum (left)

    # Update the binary index tree element(s) at index
    def Add (self, index : int, delta : int) :
        while (index < len(self.bit)) :
            self.bit[index] += delta
            index = index + (index & (-index))

    def Print_BIT (self) :
        print("\nBinary Indexed Tree array ... ")
        print(str(self.bit))

def main() :

    arr = [ 4, -5, 7, 1, -1, 2, 3, 4, -2, 6, 5, -3, 8, -6, 10 ]

    print("Array")
    print(arr)

    b = BIT(arr)
    b.Print_BIT()

    print("\n\nSum of first (14) " + str(b.Sum (14)))
    print("Sum of first (2) " + str(b.Sum (2)))
    print("Sum of first (1) " + str(b.Sum (1)))
    print("\nRange Sum : (0...4) " + str(b.Range_Sum (0, 4)))
    print("Range Sum : (4...5) " + str(b.Range_Sum (4, 5)))
    print("Range Sum : (1...2) " + str(b.Range_Sum (1, 2)))
    print("Range Sum : (5...5) " + str(b.Range_Sum (5, 5)))
    print("Range Sum : (5...7) " + str(b.Range_Sum (5, 7)))

    pos = 5
    delta = 2
    print("\nAdding 2 to element at position 5 in array")
    arr[pos-1] = arr[pos-1] + delta
    print("Updating the binary indexed tree .. ")
    b.Add(pos, delta)

    print("Array")
    print(arr)
    b.Print_BIT()
    print("\nSum of first (14) " + str(b.Sum (14)))

if __name__ == "__main__" :
    main()

Output

Array
[4, -5, 7, 1, -1, 2, 3, 4, -2, 6, 5, -3, 8, -6, 10]

Binary Indexed Tree array ... 
[0, 4, -1, 7, 7, -1, 1, 3, 15, -2, 4, 5, 6, 8, 2, 10]


Sum of first (14) 23
Sum of first (2) -1
Sum of first (1) 4

Range Sum : (0...4) 6
Range Sum : (4...5) 1
Range Sum : (1...2) 2
Range Sum : (5...5) 2
Range Sum : (5...7) 9

Adding 2 to element at position 5 in array
Updating the binary indexed tree .. 
Array
[4, -5, 7, 1, 1, 2, 3, 4, -2, 6, 5, -3, 8, -6, 10]

Binary Indexed Tree array ... 
[0, 4, -1, 7, 7, 1, 3, 3, 17, -2, 4, 5, 6, 8, 2, 10]

Sum of first (14) 25

#include<iostream>
#include<vector>

using namespace std;

class BIT {

    public:
    vector<int> bit;  // binary indexed tree

    BIT (vector<int> arr) {
        // The number of nodes in a binary indexed tree 
        // is 1 more than the elements in the array
        bit.assign (arr.size() + 1, 0);
        for (size_t i = 0; i < arr.size(); i++) {
            // Create a binary indexed tree array (bit) from the array elements
            // We fill the binary indexed from index 1
            Add (i+1, arr[i]);
        }
    }

    // Find the sum of elements from the beginning upto right.
    int Sum (int index) {
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index = index - (index & (-index));
        }
        return sum;
    }

    // Find the sum of array elements from left upto right.
    int Range_Sum (int left, int right) {
        return Sum (right + 1) - Sum (left);
    }

    // Update the binary index tree element(s) at index
    void Add (int index, int delta) {
        while (index < bit.size()) {
            bit[index] += delta;
            index = index + (index & (-index));
        }
    }

    void Print_BIT () {
        cout << "\nBinary Indexed Tree array ... " << endl;
        for (int i = 0; i < bit.size(); i++) {
            cout << "[" << i << "]:"<< bit[i] << " ";
        }
    }
};

int main() {

    vector<int> arr = { 4, -5, 7, 1, -1, 2, 3, 4, -2, 6, 5, -3, 8, -6, 10 };

    cout << "Array" << endl;
    for (int i = 0; i < arr.size(); i++) {
        cout << "[" << i << "]:" << arr[i] << " ";
    } cout << endl;

    BIT b(arr);
    b.Print_BIT();

    cout << "\n\nSum of first (14) " << b.Sum (14) << endl;
    cout << "Sum of first (2) " << b.Sum (2) << endl;
    cout << "Sum of first (1) " << b.Sum (1) << endl;
    cout << "\nRange Sum : (0...4) " << b.Range_Sum (0, 4) << endl;
    cout << "Range Sum : (4...5) " << b.Range_Sum (4, 5) << endl;
    cout << "Range Sum : (1...2) " << b.Range_Sum (1, 2) << endl;
    cout << "Range Sum : (5...5) " << b.Range_Sum (5, 5) << endl;
    cout << "Range Sum : (5...7) " << b.Range_Sum (5, 7) << endl;

    int pos = 5;
    int delta = 2;
    cout << "\nAdding 2 to element at position 5 in array" << endl;
    arr[pos-1] = arr[pos-1] + delta;
    cout << "Updating the binary indexed tree .. " << endl;
    b.Add(pos, delta);

    cout << "\nArray" << endl;
    for (int i = 0; i < arr.size(); i++) {
        cout << "[" << i << "]:" << arr[i] << " ";
    }
    b.Print_BIT();
    cout << "\n\nSum of first (14) " << b.Sum (14) << endl;

    return 0;
}

Output

Array
[0]:4 [1]:-5 [2]:7 [3]:1 [4]:-1 [5]:2 [6]:3 [7]:4 [8]:-2 [9]:6 [10]:5 [11]:-3 [12]:8 [13]:-6 [14]:10 

Binary Indexed Tree array ... 
[0]:0 [1]:4 [2]:-1 [3]:7 [4]:7 [5]:-1 [6]:1 [7]:3 [8]:15 [9]:-2 [10]:4 [11]:5 [12]:6 [13]:8 [14]:2 [15]:10 

Sum of first (14) 23
Sum of first (2) -1
Sum of first (1) 4

Range Sum : (0...4) 6
Range Sum : (4...5) 1
Range Sum : (1...2) 2
Range Sum : (5...5) 2
Range Sum : (5...7) 9

Adding 2 to element at position 5 in array
Updating the binary indexed tree .. 

Array
[0]:4 [1]:-5 [2]:7 [3]:1 [4]:1 [5]:2 [6]:3 [7]:4 [8]:-2 [9]:6 [10]:5 [11]:-3 [12]:8 [13]:-6 [14]:10 
Binary Indexed Tree array ... 
[0]:0 [1]:4 [2]:-1 [3]:7 [4]:7 [5]:1 [6]:3 [7]:3 [8]:17 [9]:-2 [10]:4 [11]:5 [12]:6 [13]:8 [14]:2 [15]:10 

Sum of first (14) 25

class BIT {

    int[] bit;  // binary indexed tree

    BIT (int[] arr) {
        // The number of nodes in a binary indexed tree 
        // is 1 more than the elements in the array
        bit = new int [arr.length + 1];
        bit[0] = 0;
        for (int i = 0; i < arr.length; i++) {
            // Create a binary indexed tree array (bit) from the array elements
            // We fill the binary indexed from index 1
            Add (i+1, arr[i]);
        }
    }

    // Find the sum of elements from the beginning upto right.
    int Sum (int index) {
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index = index - (index & (-index));
        }
        return sum;
    }

    // Find the sum of array elements from left upto right.
    int Range_Sum (int left, int right) {
        return Sum (right + 1) - Sum (left);
    }

    // Update the binary index tree element(s) at index
    void Add (int index, int delta) {
        while (index < bit.length) {
            bit[index] += delta;
            index = index + (index & (-index));
        }
    }

    void Print_BIT () {
        System.out.println( "\nBinary Indexed Tree array ... ");
        for (int i = 0; i < bit.length; i++) {
            System.out.print("[" + i + "]:"+ bit[i] + " ");
        }
    }

    public static void main (String[] arr) {

        int[] array = { 4, -5, 7, 1, -1, 2, 3, 4, -2, 6, 5, -3, 8, -6, 10 };

        System.out.println( "Array");
        for (int i = 0; i < array.length; i++) {
            System.out.print( "[" + i + "]:" + array[i] + " ");
        } System.out.println();

        BIT b = new BIT(array);
        b.Print_BIT();

        System.out.println("\n\nSum of first (14) " + b.Sum (14));
        System.out.println("Sum of first (2) " + b.Sum (2));
        System.out.println("Sum of first (1) " + b.Sum (1));
        System.out.println("\nRange Sum : (0...4) " + b.Range_Sum (0, 4));
        System.out.println("Range Sum : (4...5) " + b.Range_Sum (4, 5));
        System.out.println("Range Sum : (1...2) " + b.Range_Sum (1, 2));
        System.out.println("Range Sum : (5...5) " + b.Range_Sum (5, 5));
        System.out.println("Range Sum : (5...7) " + b.Range_Sum (5, 7));

        int pos = 5;
        int delta = 2;
        System.out.println("\nAdding 2 to element at position 5 in array");
        array[pos-1] = array[pos-1] + delta;
        System.out.println("Updating the binary indexed tree .. ");
        b.Add(pos, delta);

        System.out.println("\nArray");
        for (int i = 0; i < array.length; i++) {
            System.out.print( "[" + i + "]:" + array[i] + " ");
        }
        b.Print_BIT();
        System.out.println("\n\nSum of first (14) " + b.Sum (14));
    }
}

Output

Array
[0]:4 [1]:-5 [2]:7 [3]:1 [4]:-1 [5]:2 [6]:3 [7]:4 [8]:-2 [9]:6 [10]:5 [11]:-3 [12]:8 [13]:-6 [14]:10 

Binary Indexed Tree array ... 
[0]:0 [1]:4 [2]:-1 [3]:7 [4]:7 [5]:-1 [6]:1 [7]:3 [8]:15 [9]:-2 [10]:4 [11]:5 [12]:6 [13]:8 [14]:2 [15]:10 

Sum of first (14) 23
Sum of first (2) -1
Sum of first (1) 4

Range Sum : (0...4) 6
Range Sum : (4...5) 1
Range Sum : (1...2) 2
Range Sum : (5...5) 2
Range Sum : (5...7) 9

Adding 2 to element at position 5 in array
Updating the binary indexed tree .. 

Array
[0]:4 [1]:-5 [2]:7 [3]:1 [4]:1 [5]:2 [6]:3 [7]:4 [8]:-2 [9]:6 [10]:5 [11]:-3 [12]:8 [13]:-6 [14]:10 
Binary Indexed Tree array ... 
[0]:0 [1]:4 [2]:-1 [3]:7 [4]:7 [5]:1 [6]:3 [7]:3 [8]:17 [9]:-2 [10]:4 [11]:5 [12]:6 [13]:8 [14]:2 [15]:10 

Sum of first (14) 25