Java Program to Implement Fenwick Tree

This is a Java Program to Implement Fenwick Tree. A Fenwick tree or binary indexed tree is a data structure providing efficient methods for calculation and manipulation of the prefix sums of a table of values.

Here is the source code of the Java Program to Implement Fenwick Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
/**
```

 *  Java Program to Implement Fenwick Tree

```
 **/
```
```
  import java.util.Scanner;
```
```
 
```
```
/** Class Fenwick Tree **/
```
```
public class FenwickTree
```
```
{    
```
```
    /** Function to update tree **/
```

    private void update(int[] arr, int pos, int val)

```
    {
```
```
        int len = arr.length;
```

        for (; pos < len; pos |= (pos + 1))

```
            arr[pos] += val;
```
```
    }
```
```
    /** Function to query **/
```

    private int query(int[] arr, int pos)

```
    {
```
```
        int sum = 0;
```

        for (; pos >= 0; pos = (pos & (pos + 1)) - 1)

```
            sum += arr[pos];
```
```
 
```
```
        return sum;
```
```
    }
```
```
 
```
```
    /** Main method **/
```

    public static void main(String[] args)

```
    {
```

        Scanner scan = new Scanner( System.in );

        System.out.println("Fenwick Tree Test\n");

        /** Accept number of elements **/

        System.out.println("Enter number of integer elements");

```
        int n = scan.nextInt();
```

        /** Create integer array on n elements **/

```
        int arr[] = new int[ n ];
```
```
 
```

        FenwickTree ft = new FenwickTree();

```
 
```
```
        /** update or find sum **/
```
```
        char ch;
```
```
        do    
```
```
        {
```

            System.out.println("\nFenwick Tree Operations\n");

            System.out.println("1. update ");

            System.out.println("2. query");

```
 
```

            int choice = scan.nextInt();

```
            switch (choice)
```
```
            {
```
```
            case 1 : 
```

                System.out.println("Enter position and value to update");

                ft.update(arr, scan.nextInt(), scan.nextInt() );

                break;

```
            case 2 : 
```

                System.out.println("Enter position to find sum till nth element");

```
                try
```
```
                {
```

                    System.out.println("Sum = "+ ft.query(arr, scan.nextInt()) );

```
                }
```
```
                catch (Exception e)
```
```
                {
```

                    System.out.println("\nError! Out of bounds\n");

```
                }
```

                break;

```
            default : 
```

                System.out.println("Wrong Entry \n ");

```
                break;   
```
```
            }
```
```
 
```

            System.out.println("\nDo you want to continue (Type y or n) \n");

            ch = scan.next().charAt(0);

        } while (ch == 'Y'|| ch == 'y');

```
    }    
```
```
}
```

Fenwick Tree Test
 
Enter number of integer elements
5
 
Fenwick Tree Operations
 
1. update
2. query
1
Enter position and value to update
0 5
 
Do you want to continue (Type y or n)
 
y
 
Fenwick Tree Operations
 
1. update
2. query
1
Enter position and value to update
1 4
 
Do you want to continue (Type y or n)
 
y
 
Fenwick Tree Operations
 
1. update
2. query
1
Enter position and value to update
2 3
 
Do you want to continue (Type y or n)
 
y
 
Fenwick Tree Operations
 
1. update
2. query
1
Enter position and value to update
3 2
 
Do you want to continue (Type y or n)
 
y
 
Fenwick Tree Operations
 
1. update
2. query
1
Enter position and value to update
4 0
 
Do you want to continue (Type y or n)
 
y
 
Fenwick Tree Operations
 
1. update
2. query
2
Enter position to find sum till nth element
1
Sum = 9
 
Do you want to continue (Type y or n)
 
y
 
Fenwick Tree Operations
 
1. update
2. query
2
Enter position to find sum till nth element
2
Sum = 12
 
Do you want to continue (Type y or n)
 
y
 
Fenwick Tree Operations
 
1. update
2. query
2
Enter position to find sum till nth element
3
Sum = 14
 
Do you want to continue (Type y or n)
 
y
 
Fenwick Tree Operations
 
1. update
2. query
2
Enter position to find sum till nth element
4
Sum = 14
 
Do you want to continue (Type y or n)
 
n