Fenwick Tree
The Fenwick Tree, also known as Binary Indexed Tree (BIT), is a data structure that efficiently supports two primary operations on an array of numbers: range sum queries and element updates. It's particularly useful for solving problems where you need to maintain and query cumulative sums of elements in an array.
Problem Statement and Description
Consider scenarios where you have an array of numbers and need to answer two types of queries efficiently:
- Calculate the sum of elements in a given range [0, i].
- Update the value of an element at a specific index and propagate the change through the cumulative sum structure.
For instance, let's say you have the array [7, 3, -5, 2, 6, 1, 4, 8, 2, 3] and you want to perform
operations like finding the sum of elements in ranges [0, 3], [0, 6], [0, 4], and updating the element at index 2 to
4.
Idea to Solve the Problem
The Fenwick Tree provides an elegant solution to these types of problems by cleverly organizing the cumulative sum information to minimize the complexity of both range sum queries and updates.
Standard Pseudocode and Algorithm
Here's the standard pseudocode for constructing a Fenwick Tree and performing range sum queries and updates:
- LSB (Least Significant Bit) Function
The least significant bit function is used to isolate the lowest set bit of a number. It's crucial for navigating the Fenwick Tree structure.
function lsb(index):
return index & -index- Construct Tree Function
This function constructs the Fenwick Tree from the given array.
function construct_tree(collection, n):
index_tree = array of size (n + 1) initialized with zeros
for i from 0 to n - 1:
update(index_tree, n, i, collection[i])
return index_tree- Update Function
This function updates the Fenwick Tree when an element at a specific index is changed.
function update(index_tree, size, i, k):
if i > size:
return
index = i + 1
while index <= size:
index_tree[index] += k
index += lsb(index)- Sum Function
This function calculates the sum of elements in the range [0, i].
function sum(index_tree, size, i):
index = i + 1
total_sum = 0
while index > 0:
total_sum += index_tree[index]
index -= lsb(index)
return total_sumCode Solution
/*
C Program
Fenwick tree (Binary Indexed Tree)
*/
#include <stdio.h>
#include <stdlib.h>
// least significant bit
int lsb(int index)
{
return ((index) & -(index));
}
// returns the sum of all elements from 0 to i location
int sum(int index_tree[],int size,int i)
{
int index = i + 1;
if(index > size)
{
// When location i is invalid
return 0;
}
int sum = 0;
while (index > 0)
{
sum += index_tree[index];
index -= lsb(index);
}
// return the sum from 1 to i
return sum;
}
/*
This function is used to modification of new elements
Here i is location and k is value
*/
void changes(int index_tree[],int size,int i, int k)
{
int index = i + 1;
while (index <= size)
{
index_tree[index] += k;
index += lsb(index);
}
}
// Handles the request to construct index tree
int *construct_tree(int collection[], int n)
{
int *index_tree=(int *)malloc((n+1)*sizeof(int));
int i = 0;
// Set initial value
for (i = 0; i <= n; ++i)
{
index_tree[i] = 0;
}
for (i = 0; i < n; ++i)
{
changes(index_tree,n,i,collection[i]);
}
return index_tree;
}
// Handles the request to update element in index tree
void update(int index_tree[],int size,int i, int k)
{
if(i > size)
{
return;
}
printf("\n Update %d at location %d ",k,i);
// Add k to location i
index_tree[i] += k;
changes(index_tree,size,i,k);
}
int main()
{
int collection[] = {7,3,-5,2,6,1,4,8,2,3};
// Get the size
int n = sizeof(collection)/sizeof(collection[0]);
int *index_tree = construct_tree(collection,n);
// location
int i = 3;
// Calculate the sum of elements from 0 to i (here i = 3)
int result = sum(index_tree,n,i);
printf(" Sum of elements from 0 to %d is : %d" ,i,result);
// location
i = 6;
// Calculate the sum of elements from 0 to i (here i = 6)
result = sum(index_tree,n,i);
printf("\n Sum of elements from 0 to %d is : %d" ,i,result);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = sum(index_tree,n,i);
printf("\n Sum of elements from 0 to %d is : %d" ,i,result);
i = 2;
// i location value 4
update(index_tree,n,i,4);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = sum(index_tree,n,i);
printf("\n Sum of elements from 0 to %d is : %d" ,i,result);
return 0;
}
Output
Sum of elements from 0 to 3 is : 7
Sum of elements from 0 to 6 is : 18
Sum of elements from 0 to 4 is : 13
Update 4 at location 2
Sum of elements from 0 to 4 is : 17/*
Java Program
Fenwick tree (Binary Indexed Tree)
*/
class FenwickTree
{
// least significant bit
public int lsb(int index)
{
return ((index) & -(index));
}
// returns the sum of all elements from 0 to i location
public int sum(int[] index_tree, int size, int i)
{
// i+1 used to 0..i element
int index = i + 1;
int sum = 0;
if (index > size)
{
// When location i is invalid
return 0;
}
while (index > 0)
{
sum += index_tree[index];
index -= lsb(index);
}
// return the sum from 1 to i
return sum;
}
/*
This function is used to modification of new elements
Here i is location and k is value
*/
public void changes(int[] index_tree, int size, int i, int k)
{
int index = i + 1;
while (index <= size)
{
index_tree[index] += k;
index += lsb(index);
}
}
// Handles the request to construct index tree
public int[] construct_tree(int[] collection, int n)
{
int []index_tree = new int[n+1];
int i = 0;
// Set initial value
for (i = 0; i <= n; ++i)
{
index_tree[i] = 0;
}
for (i = 0; i < n; ++i)
{
changes(index_tree, n, i, collection[i]);
}
return index_tree;
}
// Handles the request to update element in index tree
public void update(int[] index_tree, int size, int i, int k)
{
if (i > size)
{
return;
}
System.out.print("\n Update " + k + " at location " + i + " ");
// Add k to location i
index_tree[i] += k;
changes(index_tree, size, i, k);
}
public static void main(String[] args)
{
FenwickTree tree = new FenwickTree ();
int[] collection = {
7 , 3 , -5 , 2 , 6 , 1 , 4 , 8 , 2 , 3
};
// Get the size
int n = collection.length;
int []index_tree = tree.construct_tree(collection, n);
// location
int i = 3;
// Calculate the sum of elements from 0 to i (here i = 3)
int result = tree.sum(index_tree, n, i);
System.out.print(" Sum of elements from 0 to " + i + " is : " + result );
// location
i = 6;
// Calculate the sum of elements from 0 to i (here i = 6)
result = tree.sum(index_tree, n, i);
System.out.print("\n Sum of elements from 0 to " + i + " is : " + result );
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
System.out.print("\n Sum of elements from 0 to " + i + " is : " + result );
i = 2;
// i location value 4
tree.update(index_tree, n, i, 4);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
System.out.print("\n Sum of elements from 0 to " + i + " is : " + result );
}
}Output
Sum of elements from 0 to 3 is : 7
Sum of elements from 0 to 6 is : 18
Sum of elements from 0 to 4 is : 13
Update 4 at location 2
Sum of elements from 0 to 4 is : 17// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Fenwick tree (Binary Indexed Tree)
*/
class FenwickTree
{
public:
// least significant bit
int lsb(int index)
{
return ((index) &-(index));
}
// returns the sum of all elements from 0 to i location
int sum(int index_tree[], int size, int i)
{
// return the sum from 1 to i
// i+1 used to 0..i element
int index = i + 1;
int sum = 0;
if (index > size)
{
// When location i is invalid
return 0;
}
while (index > 0)
{
sum += index_tree[index];
index -= this->lsb(index);
}
return sum;
}
/*
This function is used to modification of new elements
Here i is location and k is value
*/
void changes(int index_tree[], int size, int i, int k)
{
int index = i + 1;
while (index <= size)
{
index_tree[index] += k;
index += this->lsb(index);
}
}
// Handles the request to construct index tree
int *construct_tree(int collection[], int n)
{
int *index_tree= new int[n + 1];
int i = 0;
// Set initial value
for (i = 0; i <= n; ++i)
{
index_tree[i] = 0;
}
for (i = 0; i < n; ++i)
{
this->changes(index_tree, n, i, collection[i]);
}
return index_tree;
}
// Handles the request to update element in index tree
void update(int index_tree[], int size, int i, int k)
{
if (i > size)
{
return;
}
cout << "\n Update " << k << " at location " << i << " ";
// Add k to location i
index_tree[i] += k;
this->changes(index_tree, size, i, k);
}
};
int main()
{
FenwickTree tree = FenwickTree();
int collection[] = {
7 , 3 , -5 , 2 , 6 , 1 , 4 , 8 , 2 , 3
};
// Get the size
int n = sizeof(collection) / sizeof(collection[0]);
int *index_tree = tree.construct_tree(collection, n);
// location
int i = 3;
// Calculate the sum of elements from 0 to i (here i = 3)
int result = tree.sum(index_tree, n, i);
cout << " Sum of elements from 0 to " << i << " is : " << result;
// location
i = 6;
// Calculate the sum of elements from 0 to i (here i = 6)
result = tree.sum(index_tree, n, i);
cout << "\n Sum of elements from 0 to " << i << " is : " << result;
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
cout << "\n Sum of elements from 0 to " << i << " is : " << result;
i = 2;
// i location value 4
tree.update(index_tree, n, i, 4);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
cout << "\n Sum of elements from 0 to " << i << " is : " << result;
return 0;
}Output
Sum of elements from 0 to 3 is : 7
Sum of elements from 0 to 6 is : 18
Sum of elements from 0 to 4 is : 13
Update 4 at location 2
Sum of elements from 0 to 4 is : 17// Include namespace system
using System;
/*
C# Program
Fenwick tree (Binary Indexed Tree)
*/
public class FenwickTree
{
// least significant bit
public int lsb(int index)
{
return ((index) & -(index));
}
// returns the sum of all elements from 0 to i location
public int sum(int[] index_tree, int size, int i)
{
// return the sum from 1 to i
// i+1 used to 0..i element
int index = i + 1;
int sum = 0;
if (index > size)
{
// When location i is invalid
return 0;
}
while (index > 0)
{
sum += index_tree[index];
index -= lsb(index);
}
return sum;
}
/*
This function is used to modification of new elements
Here i is location and k is value
*/
public void changes(int[] index_tree, int size, int i, int k)
{
int index = i + 1;
while (index <= size)
{
index_tree[index] += k;
index += lsb(index);
}
}
// Handles the request to construct index tree
public int[] construct_tree(int[] collection, int n)
{
int[] index_tree = new int[n + 1];
int i = 0;
// Set initial value
for (i = 0; i <= n; ++i)
{
index_tree[i] = 0;
}
for (i = 0; i < n; ++i)
{
changes(index_tree, n, i, collection[i]);
}
return index_tree;
}
// Handles the request to update element in index tree
public void update(int[] index_tree, int size, int i, int k)
{
if (i > size)
{
return;
}
Console.Write("\n Update " + k + " at location " + i + " ");
// Add k to location i
index_tree[i] += k;
changes(index_tree, size, i, k);
}
public static void Main(String[] args)
{
FenwickTree tree = new FenwickTree();
int[] collection = {
7 , 3 , -5 , 2 , 6 , 1 , 4 , 8 , 2 , 3
};
// Get the size
int n = collection.Length;
int[] index_tree = tree.construct_tree(collection, n);
// location
int i = 3;
// Calculate the sum of elements from 0 to i (here i = 3)
int result = tree.sum(index_tree, n, i);
Console.Write(" Sum of elements from 0 to " + i + " is : " + result);
// location
i = 6;
// Calculate the sum of elements from 0 to i (here i = 6)
result = tree.sum(index_tree, n, i);
Console.Write("\n Sum of elements from 0 to " + i + " is : " + result);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
Console.Write("\n Sum of elements from 0 to " + i + " is : " + result);
i = 2;
// i location value 4
tree.update(index_tree, n, i, 4);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
Console.Write("\n Sum of elements from 0 to " + i + " is : " + result);
}
}Output
Sum of elements from 0 to 3 is : 7
Sum of elements from 0 to 6 is : 18
Sum of elements from 0 to 4 is : 13
Update 4 at location 2
Sum of elements from 0 to 4 is : 17<?php
/*
Php Program
Fenwick tree (Binary Indexed Tree)
*/
class FenwickTree
{
// least significant bit
public function lsb($index)
{
return (($index) & -($index));
}
// returns the sum of all elements from 0 to i location
public function sum( & $index_tree, $size, $i)
{
// return the sum from 1 to i
// i+1 used to 0..i element
$index = $i + 1;
$sum = 0;
if ($index > $size)
{
// When location i is invalid
return 0;
}
while ($index > 0)
{
$sum += $index_tree[$index];
$index -= $this->lsb($index);
}
return $sum;
}
/*
This function is used to modification of new elements
Here i is location and k is value
*/
public function changes( & $index_tree, $size, $i, $k)
{
$index = $i + 1;
while ($index <= $size)
{
$index_tree[$index] += $k;
$index += $this->lsb($index);
}
}
// Handles the request to construct index tree
public function construct_tree( & $collection, $n)
{
$index_tree = array_fill(0, $n + 1, 0);
$i = 0;
for ($i = 0; $i < $n; ++$i)
{
$this->changes($index_tree, $n, $i, $collection[$i]);
}
return $index_tree;
}
// Handles the request to update element in index tree
public function update( & $index_tree, $size, $i, $k)
{
if ($i > $size)
{
return;
}
echo "\n Update ". $k ." at location ". $i ." ";
// Add k to location i
$index_tree[$i] += $k;
$this->changes($index_tree, $size, $i, $k);
}
}
function main()
{
$tree = new FenwickTree();
$collection = array(7, 3, -5, 2, 6, 1, 4, 8, 2, 3);
// Get the size
$n = count($collection);
$index_tree = $tree->construct_tree($collection, $n);
// location
$i = 3;
// Calculate the sum of elements from 0 to i (here i = 3)
$result = $tree->sum($index_tree, $n, $i);
echo " Sum of elements from 0 to ". $i ." is : ". $result;
// location
$i = 6;
// Calculate the sum of elements from 0 to i (here i = 6)
$result = $tree->sum($index_tree, $n, $i);
echo "\n Sum of elements from 0 to ". $i ." is : ". $result;
// location
$i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
$result = $tree->sum($index_tree, $n, $i);
echo "\n Sum of elements from 0 to ". $i ." is : ". $result;
$i = 2;
// i location value 4
$tree->update($index_tree, $n, $i, 4);
// location
$i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
$result = $tree->sum($index_tree, $n, $i);
echo "\n Sum of elements from 0 to ". $i ." is : ". $result;
}
main();Output
Sum of elements from 0 to 3 is : 7
Sum of elements from 0 to 6 is : 18
Sum of elements from 0 to 4 is : 13
Update 4 at location 2
Sum of elements from 0 to 4 is : 17/*
Node Js Program
Fenwick tree (Binary Indexed Tree)
*/
class FenwickTree
{
// least significant bit
lsb(index)
{
return ((index) & -(index));
}
// returns the sum of all elements from 0 to i location
sum(index_tree, size, i)
{
// return the sum from 1 to i
// i+1 used to 0..i element
var index = i + 1;
var sum = 0;
if (index > size)
{
// When location i is invalid
return 0;
}
while (index > 0)
{
sum += index_tree[index];
index -= this.lsb(index);
}
return sum;
}
/*
This function is used to modification of new elements
Here i is location and k is value
*/
changes(index_tree, size, i, k)
{
var index = i + 1;
while (index <= size)
{
index_tree[index] += k;
index += this.lsb(index);
}
}
// Handles the request to construct index tree
construct_tree(collection, n)
{
var index_tree = Array(n + 1).fill(0);
var i = 0;
for (i = 0; i < n; ++i)
{
this.changes(index_tree, n, i, collection[i]);
}
return index_tree;
}
// Handles the request to update element in index tree
update(index_tree, size, i, k)
{
if (i > size)
{
return;
}
process.stdout.write("\n Update " + k + " at location " + i + " ");
// Add k to location i
index_tree[i] += k;
this.changes(index_tree, size, i, k);
}
}
function main()
{
var tree = new FenwickTree();
var collection = [7, 3, -5, 2, 6, 1, 4, 8, 2, 3];
// Get the size
var n = collection.length;
var index_tree = tree.construct_tree(collection, n);
// location
var i = 3;
// Calculate the sum of elements from 0 to i (here i = 3)
var result = tree.sum(index_tree, n, i);
process.stdout.write(" Sum of elements from 0 to " + i + " is : " + result);
// location
i = 6;
// Calculate the sum of elements from 0 to i (here i = 6)
result = tree.sum(index_tree, n, i);
process.stdout.write("\n Sum of elements from 0 to " + i + " is : " + result);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
process.stdout.write("\n Sum of elements from 0 to " + i + " is : " + result);
i = 2;
// i location value 4
tree.update(index_tree, n, i, 4);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
process.stdout.write("\n Sum of elements from 0 to " + i + " is : " + result);
}
main();Output
Sum of elements from 0 to 3 is : 7
Sum of elements from 0 to 6 is : 18
Sum of elements from 0 to 4 is : 13
Update 4 at location 2
Sum of elements from 0 to 4 is : 17# Python 3 Program
# Fenwick tree (Binary Indexed Tree)
class FenwickTree :
# least significant bit
def lsb(self, index) :
return ((index) & -(index))
# returns the sum of all elements from 0 to i location
def sum(self, index_tree, size, i) :
# i+1 used to 0..i element
index = i + 1
sum = 0
if (index > size) :
# When location i is invalid
return 0
while (index > 0) :
sum += index_tree[index]
index -= self.lsb(index)
return sum
#
# This function is used to modification of new elements
# Here i is location and k is value
#
def changes(self, index_tree, size, i, k) :
index = i + 1
while (index <= size) :
index_tree[index] += k
index += self.lsb(index)
# Handles the request to construct index tree
def construct_tree(self, collection, n) :
index_tree = [0] * (n + 1)
i = 0
while (i < n) :
self.changes(index_tree, n, i, collection[i])
i += 1
return index_tree
# Handles the request to update element in index tree
def update(self, index_tree, size, i, k) :
if (i > size) :
return
print("\n Update ", k ," at location ", i ," ", end = "")
# Add k to location i
index_tree[i] += k
self.changes(index_tree, size, i, k)
def main() :
tree = FenwickTree()
collection = [7, 3, -5, 2, 6, 1, 4, 8, 2, 3]
# Get the size
n = len(collection)
index_tree = tree.construct_tree(collection, n)
# location
i = 3
# Calculate the sum of elements from 0 to i (here i = 3)
result = tree.sum(index_tree, n, i)
print(" Sum of elements from 0 to ", i ," is : ", result, end = "")
# location
i = 6
# Calculate the sum of elements from 0 to i (here i = 6)
result = tree.sum(index_tree, n, i)
print("\n Sum of elements from 0 to ", i ," is : ", result, end = "")
# location
i = 4
# Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i)
print("\n Sum of elements from 0 to ", i ," is : ", result, end = "")
i = 2
# i location value 4
tree.update(index_tree, n, i, 4)
# location
i = 4
# Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i)
print("\n Sum of elements from 0 to ", i ," is : ", result, end = "")
if __name__ == "__main__": main()Output
Sum of elements from 0 to 3 is : 7
Sum of elements from 0 to 6 is : 18
Sum of elements from 0 to 4 is : 13
Update 4 at location 2
Sum of elements from 0 to 4 is : 17# Ruby Program
# Fenwick tree (Binary Indexed Tree)
class FenwickTree
# least significant bit
def lsb(index)
return ((index) & -(index))
end
# returns the sum of all elements from 0 to i location
def sum(index_tree, size, i)
# i+1 used to 0..i element
index = i + 1
sum = 0
if (index > size)
# When location i is invalid
return 0
end
while (index > 0)
sum += index_tree[index]
index -= self.lsb(index)
end
return sum
end
#
# This function is used to modification of new elements
# Here i is location and k is value
#
def changes(index_tree, size, i, k)
index = i + 1
while (index <= size)
index_tree[index] += k
index += self.lsb(index)
end
end
# Handles the request to construct index tree
def construct_tree(collection, n)
index_tree = Array.new(n + 1) {0}
i = 0
while (i < n)
self.changes(index_tree, n, i, collection[i])
i += 1
end
return index_tree
end
# Handles the request to update element in index tree
def update(index_tree, size, i, k)
if (i > size)
return
end
print("\n Update ", k ," at location ", i ," ")
# Add k to location i
index_tree[i] += k
self.changes(index_tree, size, i, k)
end
end
def main()
tree = FenwickTree.new()
collection = [7, 3, -5, 2, 6, 1, 4, 8, 2, 3]
# Get the size
n = collection.length
index_tree = tree.construct_tree(collection, n)
# location
i = 3
# Calculate the sum of elements from 0 to i (here i = 3)
result = tree.sum(index_tree, n, i)
print(" Sum of elements from 0 to ", i ," is : ", result)
# location
i = 6
# Calculate the sum of elements from 0 to i (here i = 6)
result = tree.sum(index_tree, n, i)
print("\n Sum of elements from 0 to ", i ," is : ", result)
# location
i = 4
# Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i)
print("\n Sum of elements from 0 to ", i ," is : ", result)
i = 2
# i location value 4
tree.update(index_tree, n, i, 4)
# location
i = 4
# Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i)
print("\n Sum of elements from 0 to ", i ," is : ", result)
end
main()Output
Sum of elements from 0 to 3 is : 7
Sum of elements from 0 to 6 is : 18
Sum of elements from 0 to 4 is : 13
Update 4 at location 2
Sum of elements from 0 to 4 is : 17/*
Scala Program
Fenwick tree (Binary Indexed Tree)
*/
class FenwickTree
{
// least significant bit
def lsb(index: Int): Int = {
return ((index) & -(index));
}
// returns the sum of all elements from 0 to i location
def sum(index_tree: Array[Int], size: Int, i: Int): Int = {
// i+1 used to 0..i element
var index: Int = i + 1;
var sum: Int = 0;
if (index > size)
{
// When location i is invalid
return 0;
}
while (index > 0)
{
sum += index_tree(index);
index -= lsb(index);
}
return sum;
}
/*
This function is used to modification of new elements
Here i is location and k is value
*/
def changes(index_tree: Array[Int], size: Int, i: Int, k: Int): Unit = {
var index: Int = i + 1;
while (index <= size)
{
index_tree(index) += k;
index += lsb(index);
}
}
// Handles the request to construct index tree
def construct_tree(collection: Array[Int], n: Int): Array[Int] = {
var index_tree: Array[Int] = Array.fill[Int](n + 1)(0);
var i: Int = 0;
while (i < n)
{
changes(index_tree, n, i, collection(i));
i += 1;
}
return index_tree;
}
// Handles the request to update element in index tree
def update(index_tree: Array[Int], size: Int, i: Int, k: Int): Unit = {
if (i > size)
{
return;
}
print("\n Update " + k + " at location " + i + " ");
// Add k to location i
index_tree(i) += k;
changes(index_tree, size, i, k);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: FenwickTree = new FenwickTree();
var collection: Array[Int] = Array(7, 3, -5, 2, 6, 1, 4, 8, 2, 3);
// Get the size
var n: Int = collection.length;
var index_tree: Array[Int] = tree.construct_tree(collection, n);
// location
var i: Int = 3;
// Calculate the sum of elements from 0 to i (here i = 3)
var result: Int = tree.sum(index_tree, n, i);
print(" Sum of elements from 0 to " + i + " is : " + result);
// location
i = 6;
// Calculate the sum of elements from 0 to i (here i = 6)
result = tree.sum(index_tree, n, i);
print("\n Sum of elements from 0 to " + i + " is : " + result);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
print("\n Sum of elements from 0 to " + i + " is : " + result);
i = 2;
// i location value 4
tree.update(index_tree, n, i, 4);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
print("\n Sum of elements from 0 to " + i + " is : " + result);
}
}Output
Sum of elements from 0 to 3 is : 7
Sum of elements from 0 to 6 is : 18
Sum of elements from 0 to 4 is : 13
Update 4 at location 2
Sum of elements from 0 to 4 is : 17/*
Swift 4 Program
Fenwick tree (Binary Indexed Tree)
*/
class FenwickTree
{
// least significant bit
func lsb(_ index: Int)->Int
{
return ((index) & -(index));
}
// returns the sum of all elements from 0 to i location
func sum(_ index_tree: [Int], _ size: Int, _ i: Int)->Int
{
// i+1 used to 0..i element
var index: Int = i + 1;
var sum: Int = 0;
if (index > size)
{
// When location i is invalid
return 0;
}
while (index > 0)
{
sum += index_tree[index];
index -= self.lsb(index);
}
return sum;
}
/*
This function is used to modification of new elements
Here i is location and k is value
*/
func changes(_ index_tree: inout[Int], _ size: Int, _ i: Int, _ k: Int)
{
var index: Int = i + 1;
while (index <= size)
{
index_tree[index] += k;
index += self.lsb(index);
}
}
// Handles the request to construct index tree
func construct_tree(_ collection: [Int], _ n: Int)->[Int]
{
var index_tree: [Int] = Array(repeating: 0, count: n + 1);
var i: Int = 0;
while (i < n)
{
self.changes(&index_tree, n, i, collection[i]);
i += 1;
}
return index_tree;
}
// Handles the request to update element in index tree
func update(_ index_tree: inout[Int], _ size: Int, _ i: Int, _ k: Int)
{
if (i > size)
{
return;
}
print("\n Update ", k ," at location ", i ," ", terminator: "");
// Add k to location i
index_tree[i] += k;
self.changes(&index_tree, size, i, k);
}
}
func main()
{
let tree: FenwickTree = FenwickTree();
let collection: [Int] = [7, 3, -5, 2, 6, 1, 4, 8, 2, 3];
// Get the size
let n: Int = collection.count;
var index_tree: [Int] = tree.construct_tree(collection, n);
// location
var i: Int = 3;
// Calculate the sum of elements from 0 to i (here i = 3)
var result: Int = tree.sum(index_tree, n, i);
print(" Sum of elements from 0 to ", i ," is : ", result, terminator: "");
// location
i = 6;
// Calculate the sum of elements from 0 to i (here i = 6)
result = tree.sum(index_tree, n, i);
print("\n Sum of elements from 0 to ", i ," is : ", result, terminator: "");
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
print("\n Sum of elements from 0 to ", i ," is : ", result, terminator: "");
i = 2;
// i location value 4
tree.update(&index_tree, n, i, 4);
// location
i = 4;
// Calculate the sum of elements from 0 to i ( here i = 4)
result = tree.sum(index_tree, n, i);
print("\n Sum of elements from 0 to ", i ," is : ", result, terminator: "");
}
main();Output
Sum of elements from 0 to 3 is : 7
Sum of elements from 0 to 6 is : 18
Sum of elements from 0 to 4 is : 13
Update 4 at location 2
Sum of elements from 0 to 4 is : 17Resultant Output Explanation
The given code implements the above pseudocode and demonstrates the use of the Fenwick Tree data structure.
- The initial array is
[7, 3, -5, 2, 6, 1, 4, 8, 2, 3]. - The constructed Fenwick Tree after initializing and updating looks like:
[0, 7, 10, -5, 7, 11, 1, 27, 2, 20, 3].
The code then performs the following operations:
- Calculates the sum of elements in the range [0, 3] which is 7.
- Calculates the sum of elements in the range [0, 6] which is 18.
- Calculates the sum of elements in the range [0, 4] which is 13.
- Updates the element at index 2 to 4, reflecting the change in the Fenwick Tree.
- Calculates the sum of elements in the range [0, 4] again, which is now 17 due to the update.
Time Complexity
The time complexity of constructing the Fenwick Tree is O(n * log n), where n is the number of elements. Both the sum and update operations have a time complexity of O(log n), which makes the Fenwick Tree efficient for handling dynamic cumulative sum queries and updates.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment