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:
Exploring the Spring Boot TestRestTemplate
Java – Get Random Item/Element From a List
Java Program to Implement Karatsuba Multiplication Algorithm
Hướng dẫn Java Design Pattern – Factory Method
Intro to the Jackson ObjectMapper
Converting String to Stream of chars
How to Use if/else Logic in Java 8 Streams
Check if a String is a Palindrome in Java
Collect a Java Stream to an Immutable Collection
Introduction to Spring Method Security
Tìm hiểu cơ chế Lazy Evaluation của Stream trong Java 8
Spring Security – security none, filters none, access permitAll
Spring Boot - Flyway Database
Sorting Query Results with Spring Data
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search
Jackson vs Gson
Spring REST API + OAuth2 + Angular
Java – Write an InputStream to a File
Spring MVC and the @ModelAttribute Annotation
Spring RestTemplate Request/Response Logging
Queue và PriorityQueue trong Java
Spring Data – CrudRepository save() Method
Unsatisfied Dependency in Spring
Tính đóng gói (Encapsulation) trong java
Call Methods at Runtime Using Java Reflection
Java Program to Implement Dijkstra’s Algorithm using Priority Queue
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
String Joiner trong Java 8
Java Program to Implement Weight Balanced Tree
Java Program to Perform String Matching Using String Library
Java Program to Implement Sorted Singly Linked List
Guide to java.util.Formatter