Prefix Sum 2D

2D prefix sum for O(1) rectangle sum queries on a static grid.

[Range Queries]|

Jul 9, 2026

|explanatory_notes.md|

#prefix-sum#2d#range-query#static-grid#inclusion-exclusion

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template <typename T = int>
vector<vector<T>> build_prefix_2d(vector<vector<T>>& matrix) {
  int n = matrix.size(), m = matrix[0].size();
  vector<vector<T>> prefix(n + 1, vector<T>(m + 1, 0));
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      prefix[i][j] = matrix[i - 1][j - 1] + prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1];
  return prefix;
}

template <typename T = int>
T query_2d(vector<vector<T>>& prefix, int x1, int y1, int x2, int y2) {
  if (x1 > x2) swap(x1, x2);
  if (y1 > y2) swap(y1, y2);
  return prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1];
}

void Solve() {
  // write your code here
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) Solve();
  return 0;
}

33 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

2D Prefix Sum — Rectangle Sum Queries

Quick Start

void Solve()
{
    int n, m; cin >> n >> m;
    vector> mat(n, vector(m));
    for (auto &row : mat)
        for (auto &x : row) cin >> x;
    auto ps = build_prefix_2d(mat);  // build 1-indexed prefix    int q; cin >> q;
    while (q--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << query_2d(ps, x1, y1, x2, y2) << "\n";
    }
}

Functions

Function	Description
`build_prefix_2d(matrix)`	Build prefix from 0-indexed matrix → 1-indexed prefix
`query_2d(prefix, x1, y1, x2, y2)`	Sum of rectangle [x1..x2]×[y1..y2]

Notes

Input matrix is 0-indexed, prefix is 1-indexed.

query_2d auto-swaps if x1 > x2 or y1 > y2.

Use ll for large sums: build_prefix_2d(mat).