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;

const int MAXN = 1005;
ll psum[MAXN][MAXN];
int N, M;

void build(ll a[][MAXN]) {
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            psum[i][j] = a[i][j] + psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1];
}

ll query(int x1, int y1, int x2, int y2) {
    if (x1 > x2) swap(x1, x2);
    if (y1 > y2) swap(y1, y2);
    return psum[x2][y2] - psum[x1-1][y2] - psum[x2][y1-1] + psum[x1-1][y1-1];
}

19 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

2D Prefix Sum

Preprocess a static $n \times m$ grid once, then answer any rectangle sum query in $O(1)$ .

Building

Construct prefix matrix $P$ where $P[i][j]$ is the sum of all elements in the sub-grid from $(1,1)$ to $(i,j)$ :

P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

Query

Sum over rectangle from $(x_1, y_1)$ to $(x_2, y_2)$ using inclusion-exclusion:

\text{sum} = P[x_2][y_2] - P[x_1-1][y_2] - P[x_2][y_1-1] + P[x_1-1][y_1-1]

When to Use

Sum queries over rectangular sub-grids in a static 2D array

Grid path counting, density queries, 2D sliding window sums

Any problem where you build once and query many times

Complexity

Build —

O(n \cdot m)

Query —

O(1)

Space —

O(n \cdot m)