Introduction

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

  suffix[i] = arr[i] + arr[i+1] + ... + arr[n-1]

  where i is the current index and n is the size of the array.
• Suffix sum works on any type of array I.E. sorted, unsorted, positive, negative, or mixed values.
• Suffix Sum is very useful in many DSA problems, such as:
  • Reverse range sum queries
  • Finding right-side contribution in arrays
  • Problems involving suffix comparisons (e.g., leaders in array)
  • Dynamic programming and greedy algorithms
• Why Suffix Sum is Useful:
  • It helps calculate the sum of any right-side subarray quickly without adding elements again and again.
  • It reduces repeated sum calculations from O(n) to O(1) using precomputed values.

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