Prefix Sum Technique: With Examples, Code and Visualization
Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.
In DSA and competitive programming, prefix sum (also called cumulative sum) is a simple yet remarkably useful technique.
A prefix sum is essentially a sequence of running totals. For an array, the prefix sum at any position is the sum of all elements up to that position. This basic concept allows us to solve complex problems with impressive efficiency.
Understanding Prefix Sum
For an array A of n elements [a₁, a₂, a₃, ..., aₙ], the prefix sum array P of length n+1 is defined as:
- P[0] = 0 (an empty sum)
- P[i] = a₁ + a₂ + a₃ + ... + aᵢ for 1 ≤ i ≤ n
In mathematical notation, this can be expressed as:
P[i] = Σⱼ₌₁ᵏ A[j] where k = i
Basic Computation of Prefix Sum
Computing a prefix sum is straightforward. We iterate through the original array, keeping a running sum that we store at each position of our prefix sum array.
Example Computation
Let's look at a concrete example:
Original array: [3, 1, 4, 1, 5, 9, 2]
The prefix sum array would be:
- P[0] = 0 (empty sum)
- P[1] = 0 + 3 = 3
- P[2] = 3 + 1 = 4
- P[3] = 4 + 4 = 8
- P[4] = 8 + 1 = 9
- P[5] = 9 + 5 = 14
- P[6] = 14 + 9 = 23
- P[7] = 23 + 2 = 25
This gives us the prefix sum array: [0, 3, 4, 8, 9, 14, 23, 25]
With this prefix sum array, we can quickly find the sum of any contiguous subarray of the original array. For example, to find the sum of elements from index 2 to index 4 (1-indexed), we calculate P[6] - P[2] = 23 - 4 =19, which equals 4 + 1 + 5 + 9.
Construction of Prefix Sum Array
Step-by-Step Algorithm
Building a prefix sum array is straightforward:
- Initialize a prefix sum array P of length n+1 (where n is the length of the original array A)
- Set P[0] = 0
- For each index i from 1 to n:
- Compute P[i] = P[i-1] + A[i-1]
Note: The indexing might differ based on whether you're using 0-indexed or 1-indexed arrays. The above algorithm assumes the original array is 0-indexed.
To calculate Prefix[1],we add original[0] = 3 to the previous sum(0).So prefix[1] = 0 +3 = 3
For Prefix[2],we add original[1] = 1 to the previous sum(3).So prefix[2] =3 +1=4.
Prefix Sum Visualization
<visualization-box>
Now, let's say we want the sum of elements in an array from index 2 to index 5. Using a normal for loop would take O(subarray size) time, since we need to iterate through each element in the range.
However, if we have a prefix sum array prepared, we can avoid iterating through each element. Since we already know the sum up to index 5, we can subtract the sum up to index 1. This effectively gives us the sum of the subarray from index 2 to 5.
So, General Formula Would Be
Sum(l,r)=prefix[r]−prefix[l−1]
Time Complexity Analysis
The construction of a prefix sum array requires a single pass through the original array, making the time complexity O(n), where n is the size of the array. The space complexity is also O(n) for storing the prefix sum array.
This linear preprocessing time is acceptable because it enables constant-time range sum queries, which is a significant advantage in many applications.
Code Implementation
Let's implement the prefix sum calculation and usage in different programming languages:
Python Implementation
def build_prefix_sum(arr):
"""
Builds a prefix sum array from the given input array.
"""
n = len(arr)
prefix_sum = [0] * (n + 1)
for i in range(n):
prefix_sum[i + 1] = prefix_sum[i] + arr[i]
return prefix_sum
def range_sum(prefix_sum, left, right):
"""
Calculates the sum of elements from index left to right (inclusive) in O(1) time.
"""
return prefix_sum[right + 1] - prefix_sum[left]
# Example usage
arr = [3, 1, 4, 1, 5, 9, 2]
prefix = build_prefix_sum(arr)
print(f"Original array: {arr}")
print(f"Prefix sum array: {prefix}")
print(f"Sum of subarray [2:5]: {range_sum(prefix, 2, 4)}") # Should be 10C++ Implementation
#include <iostream>
#include <stack>
using namespace std;
void insertSorted(stack<int>& s, int element) {
if (s.empty() || element > s.top()) {
s.push(element);
return;
}
int temp = s.top();
s.pop();
insertSorted(s, element);
s.push(temp);
}
void sortStack(stack<int>& s) {
if (s.empty()) return;
int temp = s.top();
s.pop();
sortStack(s);
insertSorted(s, temp);
}
void printStack(stack<int> s) {
if (s.empty()) return;
int x = s.top();
s.pop();
printStack(s);
cout << x << " ";
s.push(x);
}
int main() {
stack<int> s;
s.push(34);
s.push(3);
s.push(31);
s.push(98);
s.push(92);
s.push(23);
cout << "Original stack: ";
printStack(s);
cout << endl;
sortStack(s);
cout << "Sorted stack: ";
printStack(s);
cout << endl;
return 0;
}
Java Implementation
import java.util.Stack;
public class SortStack {
public static void sortStack(Stack<Integer> stack) {
if (stack.isEmpty()) return;
int temp = stack.pop();
sortStack(stack);
insertSorted(stack, temp);
}
private static void insertSorted(Stack<Integer> stack, int element) {
if (stack.isEmpty() || element > stack.peek()) {
stack.push(element);
return;
}
int temp = stack.pop();
insertSorted(stack, element);
stack.push(temp);
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(34);
stack.push(3);
stack.push(31);
stack.push(98);
stack.push(92);
stack.push(23);
System.out.println("Original stack: " + stack);
sortStack(stack);
System.out.println("Sorted stack: " + stack);
}
}
Applications of Prefix Sum
Range Sum Queries
The most direct application of prefix sums is answering range sum queries in O(1) time:
- To find the sum of elements A[i...j], compute P[j+1] - P[i]
This is far more efficient than recalculating the sum for each query, which would be O(n) per query.
Subarray Problems
Prefix sums can solve various subarray-related problems:
Finding Subarrays with Given Sum
To find a subarray with sum K, we can use prefix sums:
- Calculate the prefix sum array P
- For each prefix sum P[i], check if P[i] - K exists in the prefix sums seen so far
Maximum/MInimum Sum Subarray
- Create a prefix sum array p, where p[i] is the sum of the first i elements of the original array.
- The sum of a subarray from index i to j - 1 is p[j] - p[i].
- To find the maximum subarray sum, we need to find the maximum value of p[j] - p[i] for all i < j.
- As we iterate through the array, we keep track of the minimum value of p[i] seen so far (call it min_so_far).
- At each position j, compute p[j] - min_so_far and update the maximum result. The final answer is the largest value obtained this way.
- In the same way We can Do the minimum case aswell.
Counting Subarrays with Specific Properties
We can count subarrays with sum in a given range, subarrays with a particular average, etc., using prefix sums together with data structures like HashMaps.
Variations and Extensions
2D Prefix Sums for Matrices
The prefix sum concept extends to two-dimensional arrays (matrices):
For a matrix M of size n×m, the 2D prefix sum P at position (i,j) is the sum of all elements in the submatrix from (0,0) to (i,j):
P[i][j] = ∑ₘ₌₀ⁱ ∑ₙ₌₀ʲ M[m][n]
Step-by-Step Algorithm
Let the original 2D array be A of size m × n. We want to build a 2D prefix sum array P of size (m+1) × (n+1) where P[i][j] stores the sum of the submatrix from the top-left corner (0, 0) to (i-1, j-1) in A.
- Initialize a 2D prefix sum array P of size (m+1) × (n+1) with all zeros.
- Set P[0][*] = 0 and P[*][0] = 0 (first row and column are zeros to simplify boundary conditions).
- Loop over each cell (i, j) where 1 ≤ i ≤ m and 1 ≤ j ≤ n:
- Compute:
P[i][j]=A[i−1][j−1]+P[i−1][j]+P[i][j−1]−P[i−1][j−1]
- Compute:
To find the sum of elements in a submatrix with top-left corner (r1,c1) and bottom-right corner (r2,c2):
Sum(region) = prefixSum[r2+1][c2+1] - prefixSum[r2+1][c1] - prefixSum[r1][c2+1] + prefixSum[r1][c1]
Lets Take A Look With An Example, Lets Say we Want the sum of submatrix from (1,1) to 22)
Common Mistakes
Indexing Errors
One of the most common errors when working with prefix sums is off-by-one indexing errors:
- Remember that P[0] typically represents an empty subarray (sum 0)
- The sum of elements A[i...j] is P[j+1] - P[i], not P[j] - P[i-1]
- Double-check your array bounds, especially when switching between 0-indexed and 1-indexed arrays
Conclusion
By trading an initial O(n) preprocessing step, we gain the ability to perform range sum queries in constant time.
The power of prefix sums lies in their simplicity. With just a few lines of code, you can construct a powerful tool that solves complex problems efficiently. This technique appears frequently in competitive programming and technical interviews, making it essential for any aspiring programmer to master.
The applications of prefix sums extend far beyond simple range queries, touching areas like dynamic programming, counting problems, and even parallel computing. By understanding both the basic concept and its extensions like 2D prefix sums, you'll be well-equipped to recognize when and how to apply this technique to solve new problems.
Try implementing the examples provided in this article, and then challenge yourself with more complex problems that can benefit from this approach.
