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.

  1. /**
  2.  *  Java Program to Implement Fenwick Tree
  3.  **/
  4.   import java.util.Scanner;
  5.  
  6. /** Class Fenwick Tree **/
  7. public class FenwickTree
  8. {    
  9.     /** Function to update tree **/
  10.     private void update(int[] arr, int pos, int val) 
  11.     {
  12.         int len = arr.length;
  13.         for (; pos < len; pos |= (pos + 1)) 
  14.             arr[pos] += val;
  15.     }
  16.     /** Function to query **/
  17.     private int query(int[] arr, int pos) 
  18.     {
  19.         int sum = 0;
  20.         for (; pos >= 0; pos = (pos & (pos + 1)) - 1) 
  21.             sum += arr[pos];
  22.  
  23.         return sum;
  24.     }
  25.  
  26.     /** Main method **/
  27.     public static void main(String[] args) 
  28.     {
  29.         Scanner scan = new Scanner( System.in );        
  30.         System.out.println("Fenwick Tree Test\n");
  31.         /** Accept number of elements **/
  32.         System.out.println("Enter number of integer elements");
  33.         int n = scan.nextInt();
  34.         /** Create integer array on n elements **/
  35.         int arr[] = new int[ n ];
  36.  
  37.         FenwickTree ft = new FenwickTree();
  38.  
  39.         /** update or find sum **/
  40.         char ch;
  41.         do    
  42.         {
  43.             System.out.println("\nFenwick Tree Operations\n");
  44.             System.out.println("1. update ");
  45.             System.out.println("2. query");
  46.  
  47.             int choice = scan.nextInt();            
  48.             switch (choice)
  49.             {
  50.             case 1 : 
  51.                 System.out.println("Enter position and value to update");
  52.                 ft.update(arr, scan.nextInt(), scan.nextInt() );                     
  53.                 break;                          
  54.             case 2 : 
  55.                 System.out.println("Enter position to find sum till nth element");
  56.                 try
  57.                 {
  58.                     System.out.println("Sum = "+ ft.query(arr, scan.nextInt()) );
  59.                 }
  60.                 catch (Exception e)
  61.                 {
  62.                     System.out.println("\nError! Out of bounds\n");
  63.                 }
  64.                 break;                         
  65.             default : 
  66.                 System.out.println("Wrong Entry \n ");
  67.                 break;   
  68.             }
  69.  
  70.             System.out.println("\nDo you want to continue (Type y or n) \n");
  71.             ch = scan.next().charAt(0);                        
  72.         } while (ch == 'Y'|| ch == 'y');                                     
  73.     }    
  74. }

advertisement
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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.