# 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**

```plaintext
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**

```plaintext
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)

![](https://cdn.hashnode.com/uploads/covers/624226a5db84f8c50fa5b247/23317999-8d96-42fa-adf6-544a29d6d033.png align="left")

### 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

```cpp
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.**

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

**Step 2: Answer Queries in O(1)**

```cpp
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

![](https://cdn.hashnode.com/uploads/covers/624226a5db84f8c50fa5b247/0688a2a8-be64-4139-9e69-613d4b1d67dd.png align="center")

### 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**

```plaintext
arr = [1, 2, 3]
```

**Subarrays and their sums:**

```plaintext
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:

```cpp
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**

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

**2\. Generate Subarrays (Optimized)**

```cpp
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.