Prefix Sum 2D

Concept

2D prefix sum extends the 1D idea to a grid. pref[i][j] stores the sum of all elements in the rectangle from (1,1) to (i,j). Any rectangular subregion sum can then be computed in O(1) using inclusion-exclusion: add the full rectangle, subtract the two overlapping strips, add back the doubly-subtracted corner.

When to Use

• ▸Multiple rectangle sum queries on a static 2D grid
• ▸Forest/tree counting in a grid region
• ▸Any problem asking 'sum of values in rectangle (x1,y1) to (x2,y2)'
• ▸Reducing O(n*m) per query to O(1) per query

Intuition

Build the prefix sum grid: pref[i][j] = value + left + top - top-left (to avoid double counting). To query rectangle (x1,y1)-(x2,y2), use inclusion-exclusion: take the big rectangle pref[x2][y2], subtract the strip above and the strip to the left, then add back the corner that was subtracted twice. Drawing it on paper makes the formula click instantly.

Complexity

Template Code

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

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> pref(n+1, vector<int>(m+1, 0));
    int x;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> x;
            pref[i][j] = x + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
        }
    }

    int q, sum;
    int x1, y1, x2, y2;
    cin >> q;
    for(int i = 0; i < q; i++){
        cin >> x1 >> y1 >> x2 >> y2;
        sum = pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1];
        cout << sum << "\n";
    }

    return 0;
}

// Sample Input:
// 3 3
// 1 2 3
// 4 5 6
// 7 8 9
// 2
// 1 1 2 2
// 1 1 3 3
//
// Sample Output:
// 12
// 45