Introduction to Prefix Sum Algorithm

What is the Prefix Sum Algorithm?

The Prefix Sum Algorithm is a simple yet powerful technique that preprocesses an array to answer range-sum queries efficiently. By creating a prefix sum array, it reduces the time complexity of summing elements between any two indices from O(n) to O(1) after preprocessing.

How It Works

1. Preprocessing: Build a prefix sum array prefix[i], where each element is the sum of all elements in the original array up to index i.

   prefix[i] = prefix[i-1] + arr[i]

2. Querying: To find the sum of elements between indices l and r, use:

   sum = prefix[r] - prefix[l-1]

   For l = 0, the sum is directly prefix[r].

Why It's Useful

• Efficient Queries: Once the prefix sum array is built, any range sum query takes O(1) time.
• Optimized Solutions: Useful for problems involving multiple queries or large arrays, like subarray sums, range updates, or cumulative statistics.

Implementation

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

vector<int> buildPrefixSum(const vector<int>& arr) {
    vector<int> prefix(arr.size(), 0);
    prefix[0] = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
    return prefix;
}

int rangeSum(const vector<int>& prefix, int l, int r) {
    return l == 0 ? prefix[r] : prefix[r] - prefix[l - 1];
}

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

Example

Input: arr = [1, 2, 3, 4, 5]
Prefix Array: [1, 3, 6, 10, 15]
Query: Sum of elements from idx 1 to 3 → prefix[3] - prefix[0] = 10 - 1 = 9

Key Takeaway

The Prefix Sum Algorithm is a versatile tool for range-based computations. Its ability to preprocess data for quick queries makes it a go-to strategy for array-related problems in competitive programming and beyond.

Resources

WIP