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
Related posts:
Intro to the Jackson ObjectMapper
Java Program to Find kth Largest Element in a Sequence
How to Change the Default Port in Spring Boot
Java Program to Implement Direct Addressing Tables
Merging Two Maps with Java 8
How to Break from Java Stream forEach
Hướng dẫn sử dụng lớp Console trong java
Java Program to Implement Binary Tree
Spring Boot - Twilio
Java Program to Evaluate an Expression using Stacks
Guide to Java Instrumentation
Java TreeMap vs HashMap
Java Program to implement Dynamic Array
Java Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected
Array to String Conversions
Introduction to Spring Data JPA
Exploring the Spring Boot TestRestTemplate
Java 8 and Infinite Streams
Initialize a HashMap in Java
Java String to InputStream
Java – Generate Random String
The Dining Philosophers Problem in Java
Spring 5 Functional Bean Registration
Arrays.asList vs new ArrayList(Arrays.asList())
Using Custom Banners in Spring Boot
Hướng dẫn Java Design Pattern – Transfer Object
Java Program to Perform Stooge Sort
Java Program to Check if an UnDirected Graph is a Tree or Not Using DFS
Sort a HashMap in Java
RestTemplate Post Request with JSON
Date Time trong Java 8
Java Program to Perform Postorder Recursive Traversal of a Given Binary Tree