This content originally appeared on DEV Community and was authored by M Umair Ullah
🚀 Mastering Prefix Sum in C++: From Naive to Optimized
The Prefix Sum technique is one of the most powerful tools in array-based problems. It reduces time complexity significantly and is widely used in competitive programming, interviews, and DSA questions.
🔍 What is Prefix Sum?
The prefix sum of an array is a new array prefix[] where:
prefix[i] = arr[0] + arr[1] + ... + arr[i]
In simple terms, each index holds the cumulative sum from the start to that point.
🧠 Why Use Prefix Sum?
Prefix Sum is useful when you’re asked to compute sum of elements in a subarray multiple times efficiently.
Instead of recalculating the sum for every query, you precompute the prefix sum and answer each query in O(1).
🐢 Brute Force Approach (Naive)
❌ Time Complexity: O(N * Q)
For each query, you iterate over the subarray and calculate the sum.
cpp
int rangeSum(vector<int>& arr, int l, int r) {
int sum = 0;
for (int i = l; i <= r; i++) {
sum += arr[i];
}
return sum;
}
⚡ Optimized Approach using Prefix Sum
✅ Time Complexity: O(N) preprocessing + O(1) per query
📘 Formula:
`prefix[0] = arr[0]
prefix[i] = prefix[i-1] + arr[i]
sum of range (l, r) = prefix[r] - prefix[l-1]`
cpp
#include <iostream>
#include <vector>
using namespace std;
class PrefixSum {
public:
vector<int> computePrefixSum(vector<int>& arr) {
vector<int> prefix(arr.size());
prefix[0] = arr[0];
for (int i = 1; i < arr.size(); i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
return prefix;
}
int rangeSum(vector<int>& prefix, int l, int r) {
if (l == 0) return prefix[r];
return prefix[r] - prefix[l - 1];
}
};
int main() {
vector<int> arr = {2, 4, 6, 8, 10};
PrefixSum ps;
vector<int> prefix = ps.computePrefixSum(arr);
cout << "Sum of elements from index 1 to 3: "
<< ps.rangeSum(prefix, 1, 3) << endl; // Output: 18
return 0;
}
📊 Time & Space Complexity
Operation Time Complexity Space Complexity
Brute Force Query O(N) O(1)
Prefix Preprocess O(N) O(N)
Prefix Query O(1) O(N)
💎 Real Use Cases of Prefix Sum
- Count number of subarrays with a given sum
- Range sum queries
- 2D Prefix Sum (matrix)
- Sliding window enhancements
- Difference arrays (range update queries)
🧪 Example Problem
Problem: Given an array arr[], and multiple queries of the form (L, R), compute the sum of elements from index L to R.
Input:
arr = [1, 3, 2, 5, 4]
Queries:
(1, 3) => 3+2+5 = 10
(0, 4) => 1+3+2+5+4 = 15
Using prefix sum: Precompute prefix array once, and answer in O(1) for each query.
📦 GitHub Repository
🌟 Check out the full repository with all problems solved using Prefix Sum in C++ here:
👉 My GitHub DSA Repository - Prefix Sum
This content originally appeared on DEV Community and was authored by M Umair Ullah
M Umair Ullah | Sciencx (2025-07-29T07:16:14+00:00) ⏱️ O(N) to O(1): How Prefix Sum Will Change Your Code Forever. Retrieved from https://www.scien.cx/2025/07/29/%e2%8f%b1%ef%b8%8f-on-to-o1-how-prefix-sum-will-change-your-code-forever/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.