Prefix Sum Array - Implementation and Applications
Last Updated : 18 May, 2025
Given an array arr[] of size n, the task is to find the prefix sum of the array. A prefix sum array is another array prefixSum[] of the same size, such that prefixSum[i] is arr[0] + arr[1] + arr[2] . . . arr[i].
Examples:
Input: arr[] = [10, 20, 10, 5, 15]
Output: 10 30 40 45 60
Explanation: For each index i, add all the elements from 0 to i:
prefixSum[0] = 10,
prefixSum[1] = 10 + 20 = 30,
prefixSum[2] = 10 + 20 + 10 = 40 and so on.
Input: arr[] = [30, 10, 10, 5, 50]
Output: 30 40 50 55 105
Explanation: For each index i, add all the elements from 0 to i:
prefixSum[0] = 30,
prefixSum[1] = 30 + 10 = 40,
prefixSum[2] = 30 + 10+ 10 = 50 and so on.
Prefix Sum Implementation
The idea is to create an array prefixSum[] of size n, and for each index i in range 1 to n - 1, set prefixSum[i] = prefixSum[i - 1] + arr[i].
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; // function to find the prefix sum array vector<int> findPrefixSum(vector<int> &arr) { int n = arr.size(); // to store the prefix sum vector<int> prefixSum(n); // initialize the first element prefixSum[0] = arr[0]; // Adding present element with previous element for (int i = 1; i < n; i++) prefixSum[i] = prefixSum[i - 1] + arr[i]; return prefixSum; } int main() { vector<int> arr = {10, 20, 10, 5, 15}; vector<int> prefixSum = findPrefixSum(arr); for(auto i:prefixSum) { cout<<i<<" "; } return 0; } // Function to find the prefix sum array import java.util.*; class GfG { // Function to find the prefix sum array static ArrayList<Integer> findPrefixSum(int[] arr) { int n = arr.length; // to store the prefix sum ArrayList<Integer> prefixSum = new ArrayList<>(n); for (int i = 0; i < n; i++) { prefixSum.add(0); } // initialize the first element prefixSum.set(0, arr[0]); // Adding present element with previous element for (int i = 1; i < n; i++) prefixSum.set(i, prefixSum.get(i - 1) + arr[i]); return prefixSum; } public static void main(String[] args) { int[] arr = {10, 20, 10, 5, 15}; ArrayList<Integer> prefixSum = findPrefixSum(arr); for (int i : prefixSum) { System.out.print(i + " "); } } } # Function to find the prefix sum array def findPrefixSum(arr): n = len(arr) # to store the prefix sum prefixSum = [0] * n # initialize the first element prefixSum[0] = arr[0] # Adding present element with previous element for i in range(1, n): prefixSum[i] = prefixSum[i - 1] + arr[i] return prefixSum if __name__ == "__main__": arr = [10, 20, 10, 5, 15] prefixSum = findPrefixSum(arr) for i in prefixSum: print(i, end=" ")
// Function to find the prefix sum array using System; using System.Collections.Generic; class GfG { // Function to find the prefix sum array static List<int> findPrefixSum(int[] arr) { int n = arr.Length; // to store the prefix sum List<int> prefixSum = new List<int>(new int[n]); // initialize the first element prefixSum[0] = arr[0]; // Adding present element with previous element for (int i = 1; i < n; i++) prefixSum[i] = prefixSum[i - 1] + arr[i]; return prefixSum; } static void Main() { int[] arr = {10, 20, 10, 5, 15}; List<int> prefixSum = findPrefixSum(arr); foreach (int i in prefixSum) { Console.Write(i + " "); } } } // Function to find the prefix sum array function findPrefixSum(arr) { let n = arr.length; // to store the prefix sum let prefixSum = new Array(n).fill(0); // initialize the first element prefixSum[0] = arr[0]; // Adding present element with previous element for (let i = 1; i < n; i++) prefixSum[i] = prefixSum[i - 1] + arr[i]; return prefixSum; } let arr = [10, 20, 10, 5, 15]; let prefixSum = findPrefixSum(arr); for (let i of prefixSum) { process.stdout.write(i + " "); } Time Complexity: O(n), as we are traversing the array only once.
Auxiliary Space: O(n), to create the array prefxSum[] of size n.
Example Problems based on Prefix Sum
1. 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 i and j, Print the sum of array elements from index i to j.
Input : arr[] = {1, 2, 3, 4, 5}
i = 1, j = 3
i = 2, j = 4
Output : 9
12
Input : arr[] = {1, 2, 3, 4, 5}
i = 0, j = 4
i = 1, j = 2
Output : 15
5
Please refer Range sum queries without updates for Naive and Prefix Sum based solutions.
2. Maximum value in an array after m range increment operations:
Consider an array of size n with all initial values as 0. We need to perform the following m range increment operations.
increment(a, b, k) : Increment values from 'a' to 'b' by 'k'.
After m operations, we need to calculate the maximum of the values in the array.
Examples :
Input : n = 5 m = 3
a = 0, b = 1, k = 100
a = 1, b = 4, k = 100
a = 2, b = 3, k = 100
Output : 200
Explanation:
Initially array = {0, 0, 0, 0, 0}
After first operation: {100, 100, 0, 0, 0}
After second operation: {100, 200, 100, 100, 100}
After third operation {100, 200, 200, 200, 100}
Maximum element after m operations is 200.
Input : n = 4 m = 3
a = 1, b = 2, k = 603
a = 0, b = 0, k = 286
a = 3, b = 3, k = 882
Output : 882
Explanation:
Initially array = {0, 0, 0, 0}
After first operation: {0, 603, 603, 0}
After second operation: {286, 603, 603, 0}
After third operation: {286, 603, 603, 882}
Maximum element after m operations is 882.
Please refer Maximum after m range increment operations for details and implementation
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.
Please refer Top Problems on Prefix Sum Technique for Interviews for more prefix sum problems.
Similar Reads
DSA Tutorial - Learn Data Structures and Algorithms DSA (Data Structures and Algorithms) is the study of organizing data efficiently using data structures like arrays, stacks, and trees, paired with step-by-step procedures (or algorithms) to solve problems effectively. Data structures manage how data is stored and accessed, while algorithms focus on
7 min read
Array Data Structure Guide In this article, we introduce array, implementation in different popular languages, its basic operations and commonly seen problems / interview questions. An array stores items (in case of C/C++ and Java Primitive Arrays) or their references (in case of Python, JS, Java Non-Primitive) at contiguous
4 min read
String in Data Structure A string is a sequence of characters. The following facts make string an interesting data structure.Small set of elements. Unlike normal array, strings typically have smaller set of items. For example, lowercase English alphabet has only 26 characters. ASCII has only 256 characters.Strings are immut
3 min read
Matrix Data Structure Matrix Data Structure is a two-dimensional array arranged in rows and columns. It is commonly used to represent mathematical matrices and is fundamental in various fields like mathematics, computer graphics, and data processing. Matrices allow for efficient storage and manipulation of data in a stru
2 min read
Searching Algorithms Searching algorithms are essential tools in computer science used to locate specific items within a collection of data. In this tutorial, we are mainly going to focus upon searching in an array. When we search an item in an array, there are two most common algorithms used based on the type of input
3 min read
Sorting Algorithms A Sorting Algorithm is used to rearrange a given array or list of elements in an order. For example, a given array [10, 20, 5, 2] becomes [2, 5, 10, 20] after sorting in increasing order and becomes [20, 10, 5, 2] after sorting in decreasing order. There exist different sorting algorithms for differ
3 min read
Hashing in Data Structure Hashing is a technique used in data structures that efficiently stores and retrieves data in a way that allows for quick access. Hashing involves mapping data to a specific index in a hash table (an array of items) using a hash function. It enables fast retrieval of information based on its key. The
2 min read
Two Pointers Technique Two pointers is really an easy and effective technique that is typically used for Two Sum in Sorted Arrays, Closest Two Sum, Three Sum, Four Sum, Trapping Rain Water and many other popular interview questions. Given a sorted array arr (sorted in ascending order) and a target, find if there exists an
11 min read
Sliding Window Technique Sliding Window Technique is a method used to solve problems that involve subarray or substring or window. The main idea is to use the results of previous window to do computations for the next window. This technique is commonly used in algorithms like finding subarrays with a specific sum, finding t
13 min read
Prefix Sum Array - Implementation and Applications Given an array arr[] of size n, the task is to find the prefix sum of the array. A prefix sum array is another array prefixSum[] of the same size, such that prefixSum[i] is arr[0] + arr[1] + arr[2] . . . arr[i].Examples: Input: arr[] = [10, 20, 10, 5, 15]Output: 10 30 40 45 60Explanation: For each i
8 min read