Prefix sums

A prefix sum array stores cumulative totals so range sum [l, r] is O(1) after O(n) preprocessing—foundation for subarray sum queries and 2D grid problems.

Definition

prefix[0] = 0, prefix[i+1] = prefix[i] + a[i]. Sum l..r = prefix[r+1] - prefix[l].

Build and query

#include 
#include 

int main() {
    std::vector a = {1, 2, 3, 4};
    std::vector pre(a.size() + 1, 0);
    for (size_t i = 0; i < a.size(); ++i)
        pre[i + 1] = pre[i] + a[i];
    int l = 1, r = 2; // inclusive indices on a
    int rangeSum = pre[r + 1] - pre[l];
    std::cout << "sum[" << l << ".." << r << "] = " << rangeSum << "\n";
    return 0;
}

Use cases

• Count subarrays with sum k (with hash map)
• Equilibrium index problems
• 2D prefix for matrix region sums

Important interview questions and answers

1. Q: Space cost?
   A: O(n) extra for prefix array—trade memory for O(1) range queries.
2. Q: Off-by-one?
   A: Define whether prefix[i] sums first i elements or through i—stay consistent in interviews.

Self-check

1. How compute sum from index l to r with prefix array?
2. What is preprocessing time for prefix sums?

Pitfall: Off-by-one on prefix indices—define whether pre[i] sums first i elements.