Prefix Arrays¶

Prefix arrays store cumulative sums, so you can answer range sum queries on a static array in \(O(1)\) after \(O(n)\) preprocessing. For min/max on static ranges, see Static Array Queries. For many range add updates, use a Difference Array.

Prefix sums¶

Implementation¶

Problem: Build a prefix array to enable O(1) range sum queries.

Sample Input: arr = [1, 2, 3, 4, 5]

Sample Output:

Prefix array: [0, 1, 3, 6, 10, 15]
Range sum(1,3): 9 (2+3+4)

#include <vector>
using namespace std;

vector<int> buildPrefixArray(vector<int>& arr) {
    int n = arr.size();
    vector<int> prefix(n + 1, 0);

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

    return prefix;
}

int rangeSum(vector<int>& prefix, int left, int right) {
    return prefix[right + 1] - prefix[left];
}

Example usage¶

vector<int> arr = {1, 2, 3, 4, 5};
vector<int> prefix = buildPrefixArray(arr);
// prefix = {0, 1, 3, 6, 10, 15}

// Sum from index 1 to 3 (inclusive)
int sum_1_3 = rangeSum(prefix, 1, 3);  // 2 + 3 + 4 = 9

2D prefix arrays¶

Rectangle sum in a matrix in \(O(1)\) after \(O(n m)\) build.

#include <vector>
using namespace std;

vector<vector<int>> build2DPrefix(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    vector<vector<int>> prefix(rows + 1, vector<int>(cols + 1, 0));

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            prefix[i + 1][j + 1] = matrix[i][j] +
                                   prefix[i][j + 1] +
                                   prefix[i + 1][j] -
                                   prefix[i][j];
        }
    }

    return prefix;
}

int rectangleSum(vector<vector<int>>& prefix, int r1, int c1, int r2, int c2) {
    return prefix[r2 + 1][c2 + 1] -
           prefix[r1][c2 + 1] -
           prefix[r2 + 1][c1] +
           prefix[r1][c1];
}

Use cases¶

Range sum queries on a fixed array
Subarray problems: e.g. sum conditions, maximum subarray (with extra ideas)
2D problems: rectangle sums, grids
Cumulative totals: running sums as a building block for other algorithms

Complexity¶

Build: \(O(n)\) for 1D, \(O(n m)\) for 2D
Query: \(O(1)\) per range sum
Space: \(O(n)\) or \(O(n m)\)

Optimization tips¶

Memory layout: Contiguous arrays for cache efficiency
Modular arithmetic: Use when sums are taken modulo a number
Pair with difference arrays when the underlying array is built from many range adds