⏱️ O(N) to O(1): How Prefix Sum Will Change Your Code Forever

🚀 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