⏱️ 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