What is Applications of Prefix Sum?

In this article, we will learn Applications of Prefix Sum,This free Data Structures and Algorithms tutorial for complete beginners will help you learn Data Structures and Algorithms from scratch.

Applications of Prefix Sum

Example Problem:

Equilibrium index of an array: The equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.
Find if there is a subarray with 0 sums: Given an array of positive and negative numbers, find if there is a subarray (of size at least one) with 0 sum.
Maximum subarray size, such that all subarrays of that size have a sum less than k: Given an array of n positive integers and a positive integer k, the task is to find the maximum subarray size such that all subarrays of that size have the sum of elements less than k.
Find the prime numbers which can be written as sum of most consecutive primes: Given an array of limits. For every limit, find the prime number which can be written as the sum of the most consecutive primes smaller than or equal to the limit.
Longest Span with same Sum in two Binary arrays: Given two binary arrays, arr1[] and arr2[] of the same size n. Find the length of the longest common span (i, j) where j >= i such that arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] + arr2[i+1] + …. + arr2[j].
Maximum subarray sum modulo m: Given an array of n elements and an integer m. The task is to find the maximum value of the sum of its subarray modulo m i.e find the sum of each subarray mod m and print the maximum value of this modulo operation.
Maximum occurred integer in n ranges : Given n ranges of the form L and R, the task is to find the maximum occurring integer in all the ranges. If more than one such integer exits, print the smallest one.
Minimum cost for acquiring all coins with k extra coins allowed with every coin: You are given a list of N coins of different denominations. you can pay an amount equivalent to any 1 coin and can acquire that coin. In addition, once you have paid for a coin, we can choose at most K more coins and can acquire those for free. The task is to find the minimum amount required to acquire all the N coins for a given value of K.
Random number generator in arbitrary probability distribution fashion: Given n numbers, each with some frequency of occurrence. Return a random number with a probability proportional to its frequency of occurrence.

Related Articles:

Prefix Sum Array – Implementation and Applications in Competitive Programming

Given an array arr[] of size N, find the prefix sum of the array. A prefix sum array is another array prefixSum[] of the same size, such that the value of prefixSum[i] is arr[0] + arr[1] + arr[2] . . . arr[i].

Examples:

Input: arr[] = {10, 20, 10, 5, 15}
Output: prefixSum[] = {10, 30, 40, 45, 60}
Explanation: While traversing the array, update the element by adding it with its previous element.
prefixSum[0] = 10,
prefixSum[1] = prefixSum[0] + arr[1] = 30,
prefixSum[2] = prefixSum[1] + arr[2] = 40 and so on.

Approach: To solve the problem follow the given steps:

Declare a new array prefixSum[] of the same size as the input array
Run a for loop to traverse the input array
For each index add the value of the current element and the previous value of the prefix sum array

Below is the implementation of the above approach:

C++

// C++ program for Implementing prefix sum array
#include <bits/stdc++.h>
using namespace std;
 
// Fills prefix sum array
void fillPrefixSum(int arr[], int n, int prefixSum[])
{
    prefixSum[0] = arr[0];
    // Adding present element with previous element
    for (int i = 1; i < n; i++)
        prefixSum[i] = prefixSum[i - 1] + arr[i];
}
 
// Driver Code
int main()
{
    int arr[] = { 10, 4, 16, 20 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int prefixSum[n];
   
      // Function call
    fillPrefixSum(arr, n, prefixSum);
    for (int i = 0; i < n; i++)
        cout << prefixSum[i] << " ";
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program for Implementing prefix sum array
#include <stdio.h>
 
// Fills prefix sum array
void fillPrefixSum(int arr[], int n, int prefixSum[])
{
    prefixSum[0] = arr[0];
 
    // Adding present element with previous element
    for (int i = 1; i < n; i++)
        prefixSum[i] = prefixSum[i - 1] + arr[i];
}
 
// Driver Code
int main()
{
    int arr[] = { 10, 4, 16, 20 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int prefixSum[n];
   
      // Function call
    fillPrefixSum(arr, n, prefixSum);
    for (int i = 0; i < n; i++)
          printf("%d ", prefixSum[i]);
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java Program for Implementing prefix sum arrayclass
 
import java.io.*;
 
class Prefix {
    // Fills prefix sum array
    static void fillPrefixSum(int arr[], int n,
                              int prefixSum[])
    {
        prefixSum[0] = arr[0];
        // Adding present element with previous element
        for (int i = 1; i < n; ++i)
            prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 10, 4, 16, 20 };
        int n = arr.length;
        int prefixSum[] = new int[n];
       
          // Function call
        fillPrefixSum(arr, n, prefixSum);
        for (int i = 0; i < n; i++)
            System.out.print(prefixSum[i] + " ");
        System.out.println("");
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python3 Program for Implementing
# prefix sum array
 
# Fills prefix sum array
 
 
def fillPrefixSum(arr, n, prefixSum):
 
    prefixSum[0] = arr[0]
 
    # Adding present element
    # with previous element
    for i in range(1, n):
        prefixSum[i] = prefixSum[i - 1] + arr[i]
 
 
# Driver code
if __name__ == '__main__':
  arr = [10, 4, 16, 20]
  n = len(arr)
 
  # Function call
  prefixSum = [0 for i in range(n + 1)]
 
  fillPrefixSum(arr, n, prefixSum)
 
  for i in range(n):
      print(prefixSum[i], " ", end="")
 
# This code is contributed
# by Anant Agarwal.

C#

// C# Program for Implementing
// prefix sum arrayclass
using System;
 
class GFG {
    // Fills prefix sum array
    static void fillPrefixSum(int[] arr, int n,
                              int[] prefixSum)
    {
        prefixSum[0] = arr[0];
 
        // Adding present element
        // with previous element
        for (int i = 1; i < n; ++i)
            prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 10, 4, 16, 20 };
        int n = arr.Length;
        int[] prefixSum = new int[n];
 
          // Function call
        fillPrefixSum(arr, n, prefixSum);
 
        for (int i = 0; i < n; i++)
            Console.Write(prefixSum[i] + " ");
        Console.Write("");
    }
}
 
// This Code is Contributed by nitin mittal

Javascript

<script>
 
    // JavaScript Program for Implementing
    // prefix sum arrayclass
     
    // Fills prefix sum array
    function fillPrefixSum(arr, n, prefixSum)
    {
        prefixSum[0] = arr[0];
  
        // Adding present element
        // with previous element
        for (let i = 1; i < n; ++i)
            prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
     
    let arr = [ 10, 4, 16, 20 ];
    let n = arr.length;
    let prefixSum = new Array(n);
 
    fillPrefixSum(arr, n, prefixSum);
 
    for (let i = 0; i < n; i++)
        document.write(prefixSum[i] + " ");
    document.write("");
     
</script>

PHP

<?php
// PHP program for 
// Implementing prefix 
// sum array
 
// Fills prefix sum array
function fillPrefixSum($arr, 
                       $n)
{
    $prefixSum = array();
    $prefixSum[0] = $arr[0];
 
    // Adding present element 
    // with previous element
    for ($i = 1; $i < $n; $i++)
        $prefixSum[$i] = $prefixSum[$i - 1] + 
                                    $arr[$i];
         
    for ($i = 0; $i < $n; $i++)
        echo $prefixSum[$i] . " ";
}
 
// Driver Code
$arr = array(10, 4, 16, 20);
$n = count($arr);
 
// Function call
fillPrefixSum($arr, $n);
 
// This code is contributed
// by Sam007
?>

Output

10 14 30 50

Time Complexity: O(N)
Auxiliary Space: O(N)

Tags:

#prefix-sum #Arrays #Competitive Programming #DSA #Arrays #prefix-sum