Suffix Sum

The suffix sum array of a given array is an auxiliary array where each element is the sum of all elements to the right of that index.

This allows answering range sum queries in O(1) time.

For array a[], suffixSum[i] = a[i] + a[i+1] + … + a[n-1]

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int[] suffixSum(int[] arr) {
  int n = arr.length;
  int[] suffixSum = new int[n];

  suffixSum[n-1] = arr[n-1];
  for (int i = n-2; i >= 0; i--) {
    suffixSum[i] = suffixSum[i+1] + arr[i]; 
  }

  return suffixSum;
}

// Get sum of interval [i, j]
int sum(int i, int j, int[] suffixSum) {
  if (i == 0) return suffixSum[j];
  return suffixSum[j] - suffixSum[i-1];
} 

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
vector<int> suffixSum(vector<int> arr) {
  int n = arr.size();
  vector<int> suffixSum(n);

  suffixSum[n-1] = arr[n-1];
  for (int i = n-2; i >= 0; i--) {
    suffixSum[i] = suffixSum[i+1] + arr[i];
  }

  return suffixSum;
}

// Get sum of interval [i, j]
int sum(int i, int j, vector<int>& suffixSum) {
  if (i == 0) return suffixSum[j];
  return suffixSum[j] - suffixSum[i-1];
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def suffix_sum(arr):
  
  n = len(arr)
  suffixSum = [0] * n

  suffixSum[n-1] = arr[n-1]
  for i in range(n-2, -1, -1):
    suffixSum[i] = suffixSum[i+1] + arr[i]

  return suffixSum

# Get sum of interval [i, j]  
def sum(i, j, suffixSum):
  if i == 0: return suffixSum[j]
  return suffixSum[j] - suffixSum[i-1]

Suffix sums allow fast range queries on arrays. Useful for optimization problems.

The Suffix Sum is a derived array where the value at each position i is the sum of the numbers in the original array from position i to the end. Here’s how to calculate the Suffix Sum:

Description:

Given an array of integers, the task is to calculate the Suffix Sum.

Java:

In Java, you can calculate the Suffix Sum by iterating through the array from right to left.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class SuffixSumCalculator {
    public static int[] suffixSum(int[] numbers) {
        int[] suffixSum = new int[numbers.length];
        suffixSum[numbers.length - 1] = numbers[numbers.length - 1];
        for (int i = numbers.length - 2; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + numbers[i];
        }
        return suffixSum;
    }

    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40};
        int[] result = suffixSum(numbers);
        for (int number : result) {
            System.out.print(number + " "); // Output: 100 90 70 40
        }
    }
}

C++:

In C++, you can calculate the Suffix Sum similarly.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>

std::vector<int> suffixSum(std::vector<int>& numbers) {
    std::vector<int> suffixSum(numbers.size());
    suffixSum[numbers.size() - 1] = numbers[numbers.size() - 1];
    for (int i = numbers.size() - 2; i >= 0; i--) {
        suffixSum[i] = suffixSum[i + 1] + numbers[i];
    }
    return suffixSum;
}

int main() {
    std::vector<int> numbers = {10, 20, 30, 40};
    std::vector<int> result = suffixSum(numbers);
    for (int number : result) {
        std::cout << number << " "; // Output: 100 90 70 40
    }
    return 0;
}

Python:

In Python, the Suffix Sum can be calculated using similar logic.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def suffix_sum(numbers):
    suffix_sum = [0] * len(numbers)
    suffix_sum[-1] = numbers[-1]
    for i in range(len(numbers) - 2, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + numbers[i]
    return suffix_sum

numbers = [10, 20, 30, 40]
result = suffix_sum(numbers)
print(result) # Output: [100, 90, 70, 40]

These examples cover calculating the Suffix Sum for an array of integers in Java, C++, and Python. They create a new array where each value is the sum of the original array’s values from that index to the end.

Tabular Representation

Here’s a table that demonstrates the calculation of the suffix sum for the input array [10, 20, 30, 40].

Iteration	Current Element	Suffix Sum So Far	Resulting Suffix Sum Array
0	40	40	[-, -, -, 40]
1	30	70	[-, -, 70, 40]
2	20	90	[-, 90, 70, 40]
3	10	100	[100, 90, 70, 40]

Explanation:

Iteration 0: Starting from the last element 40, the suffix sum is 40.
Iteration 1: The next element is 30, so the suffix sum is 30 + 40 = 70.
Iteration 2: The next element is 20, so the suffix sum is 20 + 70 = 90.
Iteration 3: The first element is 10, so the suffix sum is 10 + 90 = 100.

The resulting suffix sum array is [100, 90, 70, 40], which represents the sum of all elements in the array from each corresponding position to the end.