Prefix Sum For Array (Cumulative Sum)

Use:

The prefix sum algorithm is very popular and also used in competitive programming. Mostly used in subarray sum find in constant time. 

Problem:

Given an array of integers array[L], where L is the length of the array.  you have to compute the prefix sum (prefix array) prefix[L] of array[L]. where prefix[i] represents the sum of all cells between array[0] to array[i] inclusively.

Example:

Input:

array = {1, 2, 3, 4, 5, 6, 7};

Output:

prefix Sum is:

1 3 6 10 15 21 28

Explanation:

First of all, fill the first element of the array as it is. 

Then iterate through 1 to L in the array and add the previous element of prefix[] to the coronet element using this formula.

Formula:

prefix[i] = array[i] + prefix[i - 1];

Implementation:

C++ implementation:

// C++ program for prefix sum of array

#include <bits/stdc++.h>

using namespace std;

 

// computing prefix sum

void prefixSum(vector<int> array)

{

    int L = array.size();

    vector<int> prefix(L);

 

    // copy first element of array

    prefix[0] = array[0];

    // previous element to the coronet element

    for (int i = 1; i < L; i++)

    {

        prefix[i] = array[i] + prefix[i - 1];

    }

 

    cout << "prefix Sum is:" << endl;

    for (int i = 0; i < L; i++)

    {

        cout << prefix[i] << ' ';

    }

    cout << endl;

}

 

// Driver code

int main()

{

    vector<int> array = {1, 2, 3, 4, 5, 6, 7};

    prefixSum(array);

}

 

 

Python implementation:

# python program for prefix sum of array

 

# computing prefix sum

def prefixSum(array):

    L = len(array)

    prefix = [0 for i in range(L)]

 

    # copy the first element.

    prefix[0] = array[0]

    # previous element to the coronet element

    for i in range(1, L):

        prefix[i] = array[i] + prefix[i - 1]

 

    # Display prefix sum.

    print("prefix Sum is:")

    for i in range(L):

        print(prefix[i], end=' ')

    print()

 

 

# Driver code

array = [1, 2, 3, 4, 5, 6, 7]

prefixSum(array)

 

Output:

prefix Sum is:

1 3 6 10 15 21 28

Time Complexity: O(L)  

Auxiliary Space: O(L)

where L is the length of the array.

Read more interesting articles on prefix sum:

• Prefix Sum for 2D Array
• Prefix Sum for 3D Array