.png)
Prefix Sum Technique –
1. Introduction
The Prefix Sum Technique is an efficient preprocessing method used to answer range-based queries quickly.
It works by computing cumulative sums of elements and storing them in a separate array called the prefix sum array.
Once this prefix array is built, the sum of any subarray can be obtained in constant time O(1).
This technique is widely used in:
- Array range queries
- Competitive programming
- Dynamic programming optimizations
- Interview problems involving subarrays
2. Why Prefix Sum?
Many problems ask:
- Sum of elements between two indices
- Count of elements satisfying a condition in a range
- Number of subarrays with a given sum
A naive approach recalculates sums repeatedly, leading to O(n²) time complexity.
Prefix Sum reduces this drastically by:
- Precomputing cumulative values once
- Reusing them efficiently
3. When to Use Prefix Sum
Use the Prefix Sum Technique when:
- Multiple range sum queries
- Example: Sum from index L to R
- Subarray problems
- Subarray sum equals K
- Longest subarray with given sum
- 2D matrix range queries
- Submatrix sum problems
- Frequency and difference arrays
- Counting occurrences
- Range updates
4. Basic Concept
Given an array arr of size n,
we build a prefix sum array prefix such that:
prefix[i] = arr[0] + arr[1] + ... + arr[i]
This allows us to compute the sum of elements from index L to R as:
Sum(L, R) = prefix[R] - prefix[L - 1]
If L = 0, then:
Sum(0, R) = prefix[R]
5. Illustration (Language Independent)
Example Array
arr = [2, 4, 6, 8, 10]
Prefix Sum Array Construction
Index: 0 1 2 3 4
arr: 2 4 6 8 10
prefix: 2 6 12 20 30
Range Sum Query Example
Find sum from index 1 to 3
Sum = prefix[3] - prefix[0]
= 20 - 2
= 18
Elements: 4 + 6 + 8 = 18
6. Algorithm (Prefix Sum)
Step 1: Build Prefix Sum Array
- Create a prefix array of size n
- Set prefix[0] = arr[0]
For i = 1 to n-1:
prefix[i] = prefix[i-1] + arr[i]
Step 2: Answer Range Query
- If L == 0, return prefix[R]
- Else, return prefix[R] - prefix[L - 1]
7. Why This Technique Works
- Prefix sums store cumulative information
- Any overlapping sum is reused
- Redundant calculations are eliminated
- Each range query becomes a simple subtraction
This converts repeated summation into constant time operations.
8. Example Problem
Problem Statement
Given an integer array arr and multiple queries (L, R),
find the sum of elements between indices L and R (inclusive).
9. Implementations in All Languages
C++ Implementation
#include
#include
using namespace std;
int main() {
vector arr = {2, 4, 6, 8, 10};
int n = arr.size();
vector prefix(n);
prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
int L = 1, R = 3;
int result;
if (L == 0)
result = prefix[R];
else
result = prefix[R] - prefix[L - 1];
cout << result;
return 0;
}
Output
18
C Implementation
#include
int main() {
int arr[] = {2, 4, 6, 8, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int prefix[n];
prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
int L = 1, R = 3;
int result;
if (L == 0)
result = prefix[R];
else
result = prefix[R] - prefix[L - 1];
printf("%d", result);
return 0;
}
Output
18
Java Implementation
class PrefixSum {
public static void main(String[] args) {
int[] arr = {2, 4, 6, 8, 10};
int n = arr.length;
int[] prefix = new int[n];
prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
int L = 1, R = 3;
int result;
if (L == 0)
result = prefix[R];
else
result = prefix[R] - prefix[L - 1];
System.out.println(result);
}
}
Output
18
Python Implementation
arr = [2, 4, 6, 8, 10]
n = len(arr)
prefix = [0] * n
prefix[0] = arr[0]
for i in range(1, n):
prefix[i] = prefix[i - 1] + arr[i]
L, R = 1, 3
if L == 0:
result = prefix[R]
else:
result = prefix[R] - prefix[L - 1]
print(result)
Output
18
C# Implementation
using System;
class Program {
static void Main() {
int[] arr = {2, 4, 6, 8, 10};
int n = arr.Length;
int[] prefix = new int[n];
prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
int L = 1, R = 3;
int result;
if (L == 0)
result = prefix[R];
else
result = prefix[R] - prefix[L - 1];
Console.WriteLine(result);
}
}
Output
18
JavaScript Implementation
let arr = [2, 4, 6, 8, 10];
let n = arr.length;
let prefix = new Array(n);
prefix[0] = arr[0];
for (let i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
let L = 1, R = 3;
let result;
if (L === 0)
result = prefix[R];
else
result = prefix[R] - prefix[L - 1];
console.log(result);
Output
18
10. Time and Space Complexity
| Operation | Complexity |
|---|---|
| Prefix array construction | O(n) |
| Each range query | O(1) |
| Extra space | O(n) |
11. Advanced Applications of Prefix Sum Technique
The Prefix Sum Technique is not limited to simple range sum queries. It serves as a foundational concept for solving several advanced problems efficiently.
11.1 Subarray Sum Equal to K
Problem Statement
Given an array of integers and a value K, determine whether there exists a subarray whose sum equals K.
Key Insight
Let:
prefix[i] = sum of elements from index 0 to i
If for any indices i and j (j < i):
prefix[i] - prefix[j] = K
Then the subarray (j + 1) to i has sum K.
This idea allows us to:
- Store prefix sums in a hash structure
- Check existence in constant time
Time Complexity
- O(n)
Space Complexity
- O(n)
This approach is widely used in problems involving:
- Zero sum subarrays
- Longest subarray with given sum
- Count of subarrays with sum K
11.2 Longest Subarray with Given Sum
Prefix sums can also be used to determine the maximum length subarray whose sum equals a given value.
Approach
- Compute prefix sums
- Store the first occurrence of each prefix sum
- For each index, check if (currentPrefix - target) exists
This guarantees the longest possible subarray because earlier indices give larger lengths.
11.3 Prefix Sum in Binary Arrays
Prefix sums are extremely effective for binary arrays (containing only 0s and 1s).
Common Problems
- Count subarrays with equal number of 0s and 1s
- Longest balanced subarray
- Count subarrays with sum equal to K
By converting:
0 → -1
1 → 1
These problems reduce to prefix sum difference checks.
11.4 2D Prefix Sum (Matrix Prefix Sum)
Prefix Sum can be extended to two-dimensional arrays (matrices).
Definition
Let prefix[i][j] represent the sum of all elements from (0,0) to (i,j).
Formula
prefix[i][j] = matrix[i][j]
+ prefix[i-1][j]
+ prefix[i][j-1]
- prefix[i-1][j-1]
Submatrix Sum Query
To find the sum of a submatrix with corners (r1, c1) and (r2, c2):
Sum = prefix[r2][c2]
- prefix[r1-1][c2]
- prefix[r2][c1-1]
+ prefix[r1-1][c1-1]
Use Cases
- Image processing
- Game development
- Heat maps
- Competitive programming matrix queries
11.5 Difference Array Technique (Derived from Prefix Sum)
The Difference Array is an inverse application of prefix sums, useful for range update problems.
Problem Type
- Apply multiple updates to ranges efficiently
- Example: Add X to all elements between L and R
Idea
Instead of updating every element:
diff[L] += X
diff[R + 1] -= X
Final array is obtained by computing the prefix sum of diff.
Benefit
- Range updates in O(1)
- Final array construction in O(n)
11.6 Prefix Sum vs Sliding Window
| Aspect | Prefix Sum | Sliding Window |
|---|---|---|
| Best for | Multiple queries | Single pass |
| Space | O(n) | O(1) |
| Handles negatives | Yes | Limited |
| Query time | O(1) | O(n) |
Both techniques often complement each other and are frequently used together.
12. Common Mistakes While Using Prefix Sum
- Forgetting to handle the case L = 0
- Integer overflow for large inputs
- Incorrect prefix initialization
- Using prefix sum where sliding window is more optimal
- Not accounting for negative values
13. Interview Perspective
Prefix Sum is a must-know technique for technical interviews.
Interviewers often test:
- Your ability to preprocess data
- Optimization from brute force
- Understanding of overlapping subproblems
Frequently asked variations:
- Subarray sum equals K
- Range query optimization
- Matrix sum queries
14.Summary
The Prefix Sum Technique is a powerful preprocessing method that transforms repeated calculations into constant-time operations. By storing cumulative information, it enables efficient handling of range queries, subarray problems, and matrix-based computations.
From basic range sum queries to advanced applications such as subarray sum detection, 2D matrix processing, and difference arrays, prefix sums form the backbone of many optimized algorithms. Mastering this technique significantly improves problem-solving efficiency and is essential for competitive programming, system design thinking, and technical interviews.
A strong understanding of prefix sums allows developers to convert naive O(n²) solutions into optimal O(n) or O(1) query-based approaches, making it one of the most valuable tools in algorithm design.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
