Prefix Sum Array Technique

Why Prefix Sum Array?

Prefix Sum is a powerful technique used to optimize range sum queries and many subarray problems.

In many problems, we are asked:

“Find the sum of elements between index l and r ”

Instead of recalculating sums again and again, we precompute values so that we can answered instantly.

---

What is Prefix Sum Array?

A prefix sum array is a derived array that stores the cumulative sum of elements in a given array. Each element in the prefix sum array represents the sum of all elements up to that index in the original array.

---

Step-by-Step Prefix Sum Calculation:

Given Array

arr = [2, 4, 1, 3, 5]

---

Build Prefix Sum Array

We keep adding elements cumulatively.

Index (i)	arr[i]	Running Sum	prefix[i]
0	2	2	2
1	4	2 + 4 = 6	6
2	1	6 + 1 = 7	7
3	3	7 + 3 = 10	10
4	5	10 + 5 = 15	15

---

Final Prefix Sum Array

prefix = [2, 6, 7, 10, 15]

---

Where Do We Use Prefix Sum Array?

Prefix sum is mainly used in:

1. Range Sum Queries

2. Subarray Problems

---

1. Range Sum Query (Most Common Use Case)

Problem Statement

You are given an array of size n.

You need to answer q queries:

For each query (l, r), find the sum of elements from index l to r.

---

Brute Force Approach

int q;
cin >> q;

for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;

    l--; // convert to 0-based index
    r--;

    int ans = 0;
    for (int i = l; i <= r; i++) {
        ans += arr[i];
    }

    cout << ans << endl;
}

Time Complexity

• Each query takes O(n) in worst case

• Total: O(q × n)

Worst case:

• q = 10^5

• n = 10^5

So total operations ≈ 10¹⁰ (Too slow → TLE)

---

Optimized Approach: Prefix Sum

Step 1: Build Prefix Sum Array

We create a new array where each index stores:

Sum of all elements from start to that index

Lets Build Prefix sum Array.

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += arr[i];
    arr[i] = sum;
}

Step 2: Answer Queries in O(1)

for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;

    l--; // convert to 0-based
    r--;

    if (l == 0) {
        cout << arr[r] << endl;
    } else {
        cout << arr[r] - arr[l - 1] << endl;
    }
}

---

Time Complexity

Approach	Time Complexity
Brute Force	O(q × n)
Prefix Sum	O(n + q)

Now it easily fits within 1 second limit

---

2. Sum of All Subarrays

Problem Understanding

You are given an array:

• For every starting index L, print all subarrays starting from L

• And print the sum of each subarray

Example

arr = [1, 2, 3]

Subarrays and their sums:

L = 0 → [1] = 1  
         [1,2] = 3  
         [1,2,3] = 6  

L = 1 → [2] = 2  
         [2,3] = 5  

L = 2 → [3] = 3  

---

Brute Force Approach

We generate all subarrays and calculate sum every time:

for (int l = 0; l < n; l++) {
    for (int r = l; r < n; r++) {
        int sum = 0;
        for (int k = l; k <= r; k++) {
            sum += arr[k];
        }
        cout << sum << endl;
    }
}

Time Complexity

• 3 loops → O(n³) (very slow)

---

Optimized using Prefix Sum:

Steps

1. Build Prefix Sum

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += arr[i];
    arr[i] = sum;
}

2. Generate Subarrays (Optimized)

for (int l = 0; l < n; l++) {
    for (int r = l; r < n; r++) {
        if (l == 0) {
            cout << arr[r] << endl;
        } else {
            cout << arr[r] - arr[l - 1] << endl;
        }
    }
}

Time Complexity

• Prefix building → O(n)

• Generating subarrays → O(n²)

Total = O(n²)

---

Where Else Prefix Sum is Used?

• Subarray sum problems

• Count of subarrays with given sum

• 2D matrix sum queries

• Sliding window optimizations

---

Conclusion

The prefix sum array serves as a powerful tool in optimizing computations involving cumulative sums. By constructing a prefix sum array, we can efficiently answer queries related to range sums, subarray sums etc.