# 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.

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

– Calculate the range sum of lengths 20 till 2 log2 ( 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 20 1 … 1 4
1 21 1 … 2 -1
1 22 1 … 4 7
1 23 1 … 8 15

Note : We cannot go beyond the range size 23 as 24 = 16 which is more than the length of the array. #### 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.

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 ] In the example we see that the prefix sum ( 1…14 ) can be queried in 0 ( log2 N ) time. 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.
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. 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 =  * (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

# 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 .. ")

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
}
}

// 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;

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
: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
``````
``````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;
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
}
}

// 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 .. ");

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
: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
``````