Prefix Sum in Arrays

What is Prefix Sum?

Prefix Sum is a method for dealing with array manipulation challenges. It entails establishing an auxiliary array in which each element keeps the sum of all the components preceding it(including the current element). A prefix sum array is another name for this auxiliary array.

Sample example to understand the concept:

Input: arr[] = {10, 15, 20, 25, 30}
Output: prefixSum[] = {10, 25, 45, 70, 100}

Explanation: While traversing the array, update the element by adding it to its previous element.
prefixSum[0] = 10,
prefixSum[1] = prefixSum[0] + arr[1] = 25,
prefixSum[2] = prefixSum[1] + arr[2] = 45 and so on.

Approach:

Here’s a step-by-step explanation of the approach:

1. Declare a new array prefixSum[] of the same size as the input array.
2. Initialize the first element of the prefixSum[] array to the value of the first element of the input array.
3. Run a loop to traverse the input array from the second element.
4. For each index, add the value of the current element of the input array and the previous value of the prefixSum[] array.
5. Store the sum in the current index of the prefixSum[] array.
6. After the loop finishes, return the prefixSum[] array.

Here’s an example implementation of the above approach in Java:

public static int[] prefixSum(int[] arr) {
    int n = arr.length;
    int[] prefixSum = new int[n];
    prefixSum[0] = arr[0];

    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i-1] + arr[i];
    }

    return prefixSum;
}

This function takes an input array arr and returns its prefix sum array prefixSum. The time complexity of this algorithm is O(n), where n is the size of the input array.

How to Calculate the Sum from l to r using Prefix Sums?

Once we’ve computed the prefix sum array for the input array, you can quickly compute the sum of any subarray between indices l and r in constant time using the prefix sum array.

Note: The brute force method is to find the sum using the for loop, which costs O(n) time per query. While the efficient method uses the prefixSum array to answer each query in constant time.

The steps required to find are –

1. Compute the prefix sum array for the input array using the approach discussed earlier.
2. For each query range sum query sum[l, r], do the following:
3. If l is equal to 0, then the sum of the subarray between indices l and r is simply the value of the prefix sum at index r. So, return prefixSum[r].
4. Otherwise, the sum of the subarray between indices l and r can be calculated as the difference between the value of the prefix sum at index r and the value of the prefix sum at index l-1. So, return prefixSum[r] - prefixSum[l-1].

Here’s an example implementation of the above approach in Java:

public static int rangeSumQuery(int l, int r, int[] prefixSum) {
    if (l == 0) {
        return prefixSum[r];
    }
    return prefixSum[r] - prefixSum[l-1];
}

This function takes the indices l and r for the range sum query and the prefix sum array prefixSum as input, and returns the sum of the subarray between indices l and r. The time complexity of this algorithm is O(1), which means that it can compute the sum of any subarray in constant time.

Note: also read about DSA: Concept of Array

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py