Introduction

• Suffix Sum is a way to store the sum of all elements from the current index to the end of the array.
• It is also called Reverse Cumulative Sum.
• Advantages:
  • Allows quick calculation of sums from any index to the end of the array.
  • Efficient for solving range sum queries from index i to n-1.
  • Can be combined with HashMap or prefix sum to solve problems like “count subarrays with a given sum” or maximum subarray sum from a certain point.
  • Useful in competitive programming where reverse cumulative calculations are needed.
• Why Suffix Sum is Useful:
  • Quickly computes the sum of elements from a given index to the end without iterating each time.
  • Reduces time complexity of repeated queries from O(n) to O(1) for fixed ranges.
  • Useful in DSA problems, such as:
    • Range sum queries from index i to n-1
    • Finding maximum sum of subarrays ending at a particular index
    • Complementary calculations with prefix sum for total array sum problems
    • 2D matrix problems where reverse cumulative sums are needed

Programming Examples:

1. Example 1: Calculate Suffix Sum of an Array
   • Problem: Given an array, calculate the suffix sum array.
   • Example: Array = [1, 2, 3, 4, 5], Suffix Sum = [15, 14, 12, 9, 5]

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

     Output:

     Suffix Sum Array: 15 14 12 9 5

     Note:

     • Use a new array if you need the original array for other computations.
     • Suffix sum is calculated from end to start of the array.
2. Example 2: Range Sum Query using Suffix Sum
   • Problem: Find the sum of elements from index i to the end efficiently using suffix sum.
   • Example: Array = [1, 2, 3, 4, 5], Query: sum from index 2 to 4

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

     Output:

     Sum from index 2 to end is: 12

Suffix Sum Technique Tasks:

Try below programs using Suffix Sum Technique in Java:

1. WAP to Find Sum of Elements from a Given Index to the End in O(1) Time using Suffix Sum
2. WAP to Count Subarrays where Sum of Elements from Index i to End equals a Target Value
3. WAP to Find Maximum Sum of Subarrays Ending at Each Index
4. WAP to Find the Last Equilibrium Index in an Array
5. WAP to Answer Multiple Queries of Sum from Index i to End Efficiently
6. WAP to Compute 2D Matrix Sums from Any Cell to Bottom-Right Corner using 2D Suffix Sum
7. WAP to Find Missing Number in Array using Total Sum - Suffix Sum Technique