Prefix Sum

In C++, the term "prefix sum" refers to a technique used to efficiently calculate the cumulative sum of elements in an array. The prefix sum array, also known as the cumulative sum array, stores the sum of all elements up to a certain index.

To compute the prefix sum array, you start with an initial array of numbers. Then, you iterate over the array from left to right, calculating the sum of the elements encountered so far and storing it in the corresponding position of the prefix sum array.

Here's an example to illustrate the concept. Consider the following array:

Original Array: [3, 1, 7, 4, 2, 9]

To compute the prefix sum array, you start with an empty prefix sum array and iterate over the original array:

Prefix Sum Array: [3, 4, 11, 15, 17, 26]

In this example, the prefix sum array is obtained as follows:

The first element of the prefix sum array is the same as the first element of the original array (3).

The second element of the prefix sum array is the sum of the first two elements of the original array (3 + 1 = 4).

The third element of the prefix sum array is the sum of the first three elements of the original array (3 + 1 + 7 = 11).

And so on, until you reach the end of the original array.

Once you have the prefix sum array, it can be used to quickly answer queries related to the sum of elements in subarrays. For example, to calculate the sum of elements from index 2 to index 4 (inclusive), you can simply subtract the prefix sum at index 1 from the prefix sum at index 4:

Sum of elements [2, 4]: prefixSum[4] - prefixSum[1] = 17 - 4 = 13

The prefix sum technique is particularly useful when you need to perform multiple sum queries on the same array. By precomputing the prefix sum array, you avoid redundant calculations and achieve a more efficient solution.

In C++, you can implement the prefix sum algorithm using a simple loop and an auxiliary array to store the prefix sum values.

Implementation :


#include <iostream>
#include <vector>

using namespace std;

vector<int> prefixSum(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n);
    result[0] = nums[0];
    for (int i = 1; i < n; i++) {
        result[i] = result[i-1] + nums[i];
    }
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    vector<int> result = prefixSum(nums);
    cout << "Prefix sums of nums: ";
    for (int x : result) {
        cout << x << " ";
    }
    return 0;
}

In this code, the prefixSum function takes a reference to a vector of integers nums as input and returns a vector of integers that contains the prefix sums of nums.

The result vector is initialized with the same size as nums.

The prefix sum of the first element in the sequence is simply the first element.

At each iteration, the prefix sum of the next element is calculated by adding the previous prefix sum to the current element. This sum is then stored in the result vector.

At the end of the loop, the result vector contains the prefix sums of the input nums vector. The code then prints out the prefix sums.

Why is prefix sum a better choice ?

The prefix sum approach reduces time complexity compared to traditional methods because it allows for a faster computation of the cumulative sum of any subsequence within the array using the prefix sum values.

In terms of space complexity, using the prefix sum approach reduces the amount of space required for the intermediate calculations. Rather than storing the sum of each subarray by itself, prefix sum values are used to store the cumulative sum up to that index. This means that intermediate results can be computed with minimal additional space rather than needing to store the array's entire range.

In the example code, the input sequence has n elements, and the prefix sum calculation requires O(n) time and space complexity. Once the prefix sum is calculated, the prefix sum of any subarray of nums can be calculated in constant time (O(1)). This is because the prefix sum of any subarray is the difference between two elements in the prefix sum array.

Therefore, by using the prefix sum approach, we can reduce both the time and space complexity of computations, resulting in faster and more efficient programs.

PRACTICE PROBLEMS :

Find Pivot Index

Matrix Block Sum