Introduction

• It is also known as Cumulative Sum.
• Prefix Sum is a way to store the sum of all elements from start to current index.
• For an array arr[], the prefix sum array prefix[] is defined as:

  prefix[i] = arr[0] + arr[1] + ... + arr[i]

  where i is the current index.
• Prefix sum can work with any type of array I.E. sorted, unsorted, positive, negative or mixed.
• Prefix Sum is 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
• 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).

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