Prefix and Suffix Sum

Prefix Sum:

Given an array, ‘A’ of size N, its prefix sum array is an array of the same size N such that the ith element of the prefix sum array ‘Prefix’ is the sum of all elements of the given array till ith index from the beginning, i.e Prefix[i] = A[0] + A[1] + A[2] + … + A[i]. 

For Example: Given A[] = [3, 4, -1, 2, 5], the prefix sum array P[] is given as - 

P[0] = 3, P[1] = 7, P[2] = 6, P[3] = 8, P[4] = 13

i.e. P[] = [3, 7, 6, 8, 13]

Applications:

1. Useful for answering efficiently range sum/xor queries, provided the array elements do not change over which the prefix sum/xor array is calculated.
2. Product of elements in a given range.
3. Useful for calculating maximum sum subarray and many more...

Suffix Sum:

Given an array ‘A’ of size N, its suffix sum array is an array of the same size N such that the ith element of the suffix sum array ‘Suffix’ is the sum of all elements of the given array till ith index from the end, i.e Suffix[i] = A[i] + A[i+1] + A[i+2] + … + A[N-1] - (0-Based indexing).

For Example: Given A[] = [3, 4, -1, 2, 5], the suffix sum array S[] is given as - 

S[0] = 13, S[1] = 10, S[2] = 6, S[3] = 7, S[4] = 5.

i.e. S[] = [13, 10, 6, 7, 5]

Suffix sum array can serve the same applications as prefix sum array, as it works in a similar manner to prefix sum array.