Prefix Sum Pattern

The Prefix Sum pattern involves preprocessing an array to create a new array where each element at index i represents the sum of all elements from the start of the array up to index i. This technique allows for efficient sum queries on subarrays in constant time.

When to Use This Pattern

• When you need to perform multiple sum queries on subarrays
• When you need to calculate cumulative sums efficiently
• When dealing with range sum queries
• When optimizing problems that require repeated subarray sum calculations

Key Concepts

The fundamental idea is to precompute a prefix sum array P where:

\[ P[i] = \sum_{j=0}^{i} A[j] = A[0] + A[1] + \ldots + A[i] \]

Once we have this prefix array, we can calculate the sum of any subarray from index i to j in constant time using:

\[ \text{Sum}(i, j) = P[j] - P[i-1] \]

For the special case when i = 0, the sum is simply P[j].

Visual Representation

Step-by-Step Simulation

Let's trace through building a prefix sum array with A = [1, 2, 3, 4, 5]:

Query Simulation

Now let's query the sum from index 1 to 3:

Algorithm Section

Building the Prefix Sum Array

The algorithm to build a prefix sum array is straightforward:

function buildPrefixSum(arr):
    n = length(arr)
    prefix = new array of size n
    prefix[0] = arr[0]
    
    for i from 1 to n-1:
        prefix[i] = prefix[i-1] + arr[i]
    
    return prefix

Querying Subarray Sum

To get the sum of elements from index i to j (inclusive):

function rangeSum(prefix, i, j):
    if i == 0:
        return prefix[j]
    else:
        return prefix[j] - prefix[i-1]

Time and Space Complexity

• Time Complexity: \(O(n)\) to build the prefix array, \(O(1)\) per query
• Space Complexity: \(O(n)\) for storing the prefix array

Implementation in C++

#include <iostream>
#include <vector>
using namespace std;

// Build prefix sum array
vector<int> buildPrefixSum(const vector<int>& arr) {
    int n = arr.size();
    vector<int> prefix(n);
    prefix[0] = arr[0];
    
    // Build prefix sum: each element is sum of all previous + current
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i-1] + arr[i];
    }
    
    return prefix;
}

// Query range sum from index i to j (inclusive)
int rangeSum(const vector<int>& prefix, int i, int j) {
    // If starting from index 0, prefix[j] is the answer
    if (i == 0) {
        return prefix[j];
    }
    // Otherwise, subtract prefix[i-1] to exclude elements before i
    return prefix[j] - prefix[i-1];
}

// Example usage
int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    vector<int> prefix = buildPrefixSum(arr);
    
    cout << "Prefix array: ";
    for (int val : prefix) {
        cout << val << " ";
    }
    cout << endl;
    
    cout << "Sum from index 1 to 3: " << rangeSum(prefix, 1, 3) << endl;
    // Output: 9
    
    return 0;
}

Detailed Explanation of C++ Implementation

• buildPrefixSum: Creates a prefix array where each element stores the cumulative sum up to that index. We start with prefix[0] = arr[0], then for each subsequent index i, we add arr[i] to the previous prefix sum.
• rangeSum: To get the sum from index i to j, we use prefix[j] - prefix[i-1]. This works because prefix[j] contains the sum of all elements from 0 to j, and prefix[i-1] contains the sum from 0 to i-1. Subtracting them gives us the sum from i to j.
• Edge Case: When i = 0, we simply return prefix[j] since there are no elements before index 0 to subtract.