Introduction

• Prefix Sum is a way to store the sum of all elements from start to current index.
• It is also called Cumulative Sum.
• Advantages:
  • It avoids repeated addition of elements.
  • It is efficient for range sum queries.
  • It can be combined with HashMap to solve advanced problems like “count subarrays with a given sum”.
• Why Prefix Sum is Useful:
  • It helps calculate sum of any subarray quickly without adding elements every time.
  • Reduces the time complexity of repeated sum queries from O(n) to O(1).
  • Very useful in DSA problems, like:
    • Range sum queries
    • Counting subarrays with a given sum
    • Maximum sum subarray of fixed length
    • 2D matrix sum queries

Programming Examples:

1. Example 1: Calculate Prefix Sum of an Array
   • Problem: Given an array, calculate the prefix sum array.
   • Example: Array = [1, 2, 3, 4, 5], Prefix Sum = [1, 3, 6, 10, 15]

     public class PrefixSumExample
     {
         public static void main(String[] args)
         {
             int[] arr = {1, 2, 3, 4, 5};
             int n = arr.length;
             int[] prefix = new int[n];
     
             prefix[0] = arr[0]; // first element
             for (int i = 1; i < n; i++)
             {
                 prefix[i] = prefix[i - 1] + arr[i]; // cumulative sum
             }
     
             // Print prefix sum array
             System.out.println("Prefix Sum Array:");
             for (int i = 0; i < n; i++)
             {
                 System.out.print(prefix[i] + " ");
             }
         }
     }

     Output:

     Prefix Sum Array: 1 3 6 10 15

     Note:

     • Use a new array if you need the original values for later computations.
     • Use in-place if you only need the cumulative sums and want to save memory.
2. Example 2: Range Sum Query using Prefix Sum
   • Problem: Find the sum of elements between two indices (l, r) efficiently.
   • Example: Array = [1, 2, 3, 4, 5], Query: sum from index 1 to 3

     public class RangeSumQuery
     {
         public static void main(String[] args)
         {
             int[] arr = {1, 2, 3, 4, 5};
             int n = arr.length;
             int[] prefix = new int[n];
     
             // Build prefix sum array
             prefix[0] = arr[0];
             for (int i = 1; i < n; i++)
             {
                 prefix[i] = prefix[i - 1] + arr[i];
             }
     
             // Query sum from index 1 to 3
             int l = 1, r = 3;
             int sum;
             if (l == 0)
             {
                 sum = prefix[r];
             }
             else
             {
                 sum = prefix[r] - prefix[l - 1];
             }
     
             System.out.println("Sum from index " + l + " to " + r + " is: " + sum);
         }
     }

     Output:

     Sum from index 1 to 3 is: 9

Prefix Sum Technique Tasks:

Try below programs using Prefix Sum Technique in Java:

1. WAP to Find Sum of Any Subarray in O(1) Time using Prefix Sum
2. WAP to Count the Number of Subarrays with a Given Sum
3. WAP to Find Maximum Sum Subarray of Fixed Length
4. WAP to Find Equilibrium Index in an Array
5. WAP to Answer Multiple Range Sum Queries Efficiently
6. WAP to Compute 2D Matrix Sum Queries using 2D Prefix Sum
7. WAP to Find Missing Number in Array using Prefix Sum