Range Sum Query using Prefix Sum
This program answers range sum queries using prefix sums.
Problem Statement
Write a Java program to calculate sum of elements between index 1 and 3 using prefix sums.
Source Code
| 1 | public class RangeSumQuery { |
| 2 | public static void main(String[] args) { |
| 3 | System.out.println("Eduinq Range Sum Query"); |
| 4 | int[] arr = {1,2,3,4,5}; |
| 5 | int[] prefix = new int[arr.length]; |
| 6 | prefix[0] = arr[0]; |
| 7 | for(int i=1;i<arr.length;i++){ |
| 8 | prefix[i] = prefix[i-1] + arr[i]; |
| 9 | } |
| 10 | int l=1, r=3; |
| 11 | int sum = prefix[r] - (l>0 ? prefix[l-1] : 0); |
| 12 | System.out.println("Sum from index "+l+" to "+r+" = "+sum); |
| 13 | } |
| 14 | } |
Program Output
Eduinq Range Sum Query Sum from index 1 to 3 = 9
Explanation
Prefix sums are precomputed to store cumulative totals, and any range sum can then be calculated as prefix[r] minus prefix[l-1], answering the query in constant time after preprocessing, demonstrating a prefix sum application.