Fenwick Tree

Here given code implementation process.

/*
    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 :  17


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







© 2021, kalkicode.com, All rights reserved