Prefix Sum Array – Implementation and Applications in Competitive Programming
Last Updated :
16 Jan, 2024
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++
#include <bits/stdc++.h>
using namespace std;
void fillPrefixSum(int arr[], int n, int prefixSum[])
{
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
int main()
{
int arr[] = { 10, 4, 16, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
int prefixSum[n];
fillPrefixSum(arr, n, prefixSum);
for (int i = 0; i < n; i++)
cout << prefixSum[i] << " ";
}
|
C
#include <stdio.h>
void fillPrefixSum(int arr[], int n, int prefixSum[])
{
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
int main()
{
int arr[] = { 10, 4, 16, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
int prefixSum[n];
fillPrefixSum(arr, n, prefixSum);
for (int i = 0; i < n; i++)
printf("%d ", prefixSum[i]);
}
|
Java
import java.io.*;
class Prefix {
static void fillPrefixSum(int arr[], int n,
int prefixSum[])
{
prefixSum[0] = arr[0];
for (int i = 1; i < n; ++i)
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
public static void main(String[] args)
{
int arr[] = { 10, 4, 16, 20 };
int n = arr.length;
int prefixSum[] = new int[n];
fillPrefixSum(arr, n, prefixSum);
for (int i = 0; i < n; i++)
System.out.print(prefixSum[i] + " ");
System.out.println("");
}
}
|
Python3
def fillPrefixSum(arr, n, prefixSum):
prefixSum[0] = arr[0]
for i in range(1, n):
prefixSum[i] = prefixSum[i - 1] + arr[i]
if __name__ == '__main__':
arr = [10, 4, 16, 20]
n = len(arr)
prefixSum = [0 for i in range(n + 1)]
fillPrefixSum(arr, n, prefixSum)
for i in range(n):
print(prefixSum[i], " ", end="")
|
C#
using System;
class GFG {
static void fillPrefixSum(int[] arr, int n,
int[] prefixSum)
{
prefixSum[0] = arr[0];
for (int i = 1; i < n; ++i)
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
public static void Main()
{
int[] arr = { 10, 4, 16, 20 };
int n = arr.Length;
int[] prefixSum = new int[n];
fillPrefixSum(arr, n, prefixSum);
for (int i = 0; i < n; i++)
Console.Write(prefixSum[i] + " ");
Console.Write("");
}
}
|
Javascript
<script>
function fillPrefixSum(arr, n, prefixSum)
{
prefixSum[0] = arr[0];
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
function fillPrefixSum($arr,
$n)
{
$prefixSum = array();
$prefixSum[0] = $arr[0];
for ($i = 1; $i < $n; $i++)
$prefixSum[$i] = $prefixSum[$i - 1] +
$arr[$i];
for ($i = 0; $i < $n; $i++)
echo $prefixSum[$i] . " ";
}
$arr = array(10, 4, 16, 20);
$n = count($arr);
fillPrefixSum($arr, $n);
?>
|
Time Complexity: O(N)
Auxiliary Space: O(N)
Sum of an array between indexes L and R using Prefix Sum:
Given an array arr[] of size N. Given Q queries and in each query given L and R, Print the sum of array elements from index L to R.
Follow the given steps to solve the problem:
- Create the prefix sum array of the given input array
- Now for every query (1-based indexing)
- If L is greater than 1, then print prefixSum[R] – prefixSum[L-1]
- else print prefixSum[R]
Below is the implementation of the above approach.
C++14
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int pf[N];
int main()
{
int n = 6;
int a[] = { 3, 6, 2, 8, 9, 2 };
pf[0] = a[0];
for (int i = 1; i < n; i++) {
pf[i] = pf[i - 1] + a[i];
}
int q = 4;
vector<vector<int> > query
= { { 2, 3 }, { 4, 6 }, { 1, 5 }, { 3, 6 } };
for (int i = 0; i < q; i++) {
int l = query[i][0], r = query[i][1];
if (r > n || l < 1) {
cout << "Please input in range 1 to " << n
<< endl;
continue;
}
if (l == 1)
cout << pf[r - 1] << endl;
else
cout << pf[r - 1] - pf[l - 2] << endl;
}
return 0;
}
|
Java
import java.util.*;
class GFG {
public static void main(String[] args)
{
int n = 6;
int[] a = { 3, 6, 2, 8, 9, 2 };
int[] pf = new int[n + 2];
pf[0] = 0;
for (int i = 0; i < n; i++) {
pf[i + 1] = pf[i] + a[i];
}
int[][] q
= { { 2, 3 }, { 4, 6 }, { 1, 5 }, { 3, 6 } };
for (int i = 0; i < q.length; i++) {
int l = q[i][0];
int r = q[i][1];
System.out.print(pf[r] - pf[l - 1] + "\n");
}
}
}
|
Python3
if __name__ == '__main__':
n = 6
a = [3, 6, 2, 8, 9, 2]
pf = [0 for i in range(n+2)]
for i in range(n):
pf[i + 1] = pf[i] + a[i]
q = [[2, 3], [4, 6], [1, 5], [3, 6]]
for i in range(4):
l = q[i][0]
r = q[i][1]
print(pf[r] - pf[l - 1])
|
C#
using System;
public class GFG {
public static void Main(String[] args)
{
int n = 6;
int[] a = { 3, 6, 2, 8, 9, 2 };
int[] pf = new int[n + 2];
pf[0] = 0;
for (int i = 0; i < n; i++) {
pf[i + 1] = pf[i] + a[i];
}
int[, ] q
= { { 2, 3 }, { 4, 6 }, { 1, 5 }, { 3, 6 } };
for (int i = 0; i < q.GetLength(0); i++) {
int l = q[i, 0];
int r = q[i, 1];
Console.Write(pf[r] - pf[l - 1] + "\n");
}
}
}
|
Javascript
<script>
var n = 6;
var a = [ 3, 6, 2, 8, 9, 2 ];
var pf = Array(n+2).fill(0);
pf[0] = 0;
for (i = 0; i < n; i++) {
pf[i+1] = pf[i] + a[i];
}
var q = [ [ 2, 3 ], [ 4, 6 ], [ 1, 5 ], [ 3, 6 ] ];
for (i = 0; i < q.length; i++) {
var l = q[i][0];
var r = q[i][1];
document.write(pf[r] - pf[l - 1] + "<br/>");
}
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(N)
Example Problem:
Consider an array of size N with all initial values as 0. Perform the given ‘m’ add operations from index ‘a’ to ‘b’ and evaluate the highest element in the array. An add operation adds 100 to all the elements from a to b (both inclusive).
Example:
Input: n = 5, m = 3
a = 2, b = 4.
a = 1, b = 3.
a = 1, b = 2.
Output: 300
Explanation:
After I operation – A[] = {0, 100, 100, 100, 0}
After II operation – A[] = {100, 200, 200, 100, 0}
After III operation – A[] = {200, 300, 200, 100, 0}
Highest element: 300
Naive Approach: To solve the problem follow the below idea:
A simple approach is running a loop ‘m’ times. Inputting a and b and running a loop from a to b, adding all elements by 100.
Time Complexity: O(N * M)
Auxiliary Space: O(1)
Efficient Approach: To solve the problem follow the below idea:
The efficient approach is to use Prefix Sum Array
Follow the given steps to solve the problem:
- Run a loop for ‘m‘ times, inputting ‘a‘ and ‘b‘.
- Add 100 at index ‘a-1‘ and subtract 100 from index ‘b‘.
- After completion of ‘m‘ operations, compute the prefix sum array.
- Scan the largest element and we’re done.
Explanation: We added 100 at ‘a’ because this will add 100 to all elements while taking the prefix sum array. Subtracting 100 from ‘b+1’ will reverse the changes made by adding 100 to elements from ‘b’ onward.
Below is the illustration of the above approach:
After I operation –
A[] = {0, 100, 0, 0, -100}
After II operation –
A[] = {100, 100, 0, -100, -100}
After III operation –
A[] = {200, 100, -100, -100, -100}
Final Prefix Sum Array : 200 300 200 100 0
The required highest element : 300
Below is the implementation of the above approach:
C++14
#include <bits/stdc++.h>
using namespace std;
int find(int m, vector<pair<int, int> > q)
{
int mx = 0;
vector<int> pre(5, 0);
for (int i = 0; i < m; i++) {
int a = q[i].first, b = q[i].second;
pre[a - 1] += 100;
pre[b] -= 100;
}
for (int i = 1; i < 5; i++) {
pre[i] += pre[i - 1];
mx = max(mx, pre[i]);
}
return mx;
}
int main()
{
int m = 3;
vector<pair<int, int> > q
= { { 2, 4 }, { 1, 3 }, { 1, 2 } };
cout << find(m, q);
return 0;
}
|
Java
import java.util.*;
class GFG {
static class pair {
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static int find(int m, pair[] q)
{
int mx = 0;
int[] pre = new int[5];
for (int i = 0; i < m; i++) {
int a = q[i].first, b = q[i].second;
pre[a - 1] += 100;
pre[b] -= 100;
}
for (int i = 1; i < 5; i++) {
pre[i] += pre[i - 1];
mx = Math.max(mx, pre[i]);
}
return mx;
}
public static void main(String[] args)
{
int m = 3;
pair[] q = { new pair(2, 4), new pair(1, 3),
new pair(1, 2) };
System.out.print(find(m, q));
}
}
|
Python3
def find(m, q):
mx = 0
pre = [0 for i in range(5)]
for i in range(m):
a, b = q[i][0], q[i][1]
pre[a-1] += 100
pre[b] -= 100
for i in range(1, 5):
pre[i] += pre[i - 1]
mx = max(mx, pre[i])
return mx
m = 3
q = [[2, 4], [1, 3], [1, 2]]
print(find(m, q))
|
C#
using System;
public class GFG {
public class pair {
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static int find(int m, pair[] q)
{
int mx = 0;
int[] pre = new int[5];
for (int i = 0; i < m; i++) {
int a = q[i].first, b = q[i].second;
pre[a - 1] += 100;
pre[b] -= 100;
}
for (int i = 1; i < 5; i++) {
pre[i] += pre[i - 1];
mx = Math.Max(mx, pre[i]);
}
return mx;
}
public static void Main(String[] args)
{
int m = 3;
pair[] q = { new pair(2, 4), new pair(1, 3),
new pair(1, 2) };
Console.Write(find(m, q));
}
}
|
Javascript
<script>
function find( m,q)
{
let mx = 0;
let pre = [0,0,0,0,0];
for (let i = 0; i < m; i++)
{
let a = q[i][0], b = q[i][1];
pre[a-1] += 100;
pre[b] -=100;
}
for (let i = 1; i < 5; i++)
{
pre[i] += pre[i - 1];
mx = Math.max(mx, pre[i]);
}
return mx;
}
let m = 3;
let q = [[2,4],[1,3],[1,2]];
document.write(find(m,q));
</script>
|
Time Complexity: O(N + M), where N is the size of the array and M is the number of operations
Auxiliary Space: O(N)
Applications of Prefix Sum:
- 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:
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...