Skip to main content

Fenwick Tree

Fenwick Tree, also known as Binary Indexed Tree (BIT), is a data structure used for efficiently calculating prefix sums and updating individual elements in an array. It was developed by Peter Fenwick in 1994.

The Fenwick Tree is a binary tree where each node stores the sum of a range of elements in an array. The tree is constructed by assigning each element in the array to a node in the tree, and the parent of a node is the node that represents the range that contains its range.

The key advantage of the Fenwick Tree is that it allows for efficient updates and queries of prefix sums. Updating an element in the array requires updating the corresponding node and all its ancestors in the tree, which can be done in O(log n) time complexity. Similarly, calculating the prefix sum of a range requires accessing only O(log n) nodes in the tree.

Fenwick Trees are commonly used in applications such as range sum queries, counting inversions in an array, and solving dynamic programming problems.

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




Comment

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