Submatrix Sum in O(1) - Tutorial by Md. Emrul Chowdhury

In this tutorial, I'm going to describe a problem and a simple solution to solve this to learn two dimensional cumulative sums.

Problem Statement

You have a 2D matrix mat having n rows and m columns. You have some assigned numbers in every cell.

You need to do some queries, in every query you need to print the sum of the submatrix. You will be given the position of upper left cell and lower right cell of the matrix.

Example Matrix:

	Col 1	Col 2	Col 3	Col 4	Col 5	Col 6
Row 1	3	5	1	16	8	13
Row 2	12	2	13	9	11	6
Row 3	7	10	6	12	4	7
Row 4	11	6	17	4	7	18
Row 5	8	14	7	8	12	3

Query Example: Find the sum of submatrix from (2,3) to (4,5) - highlighted cells above.

Solution Approaches

Naive Approach

Let's solve this problem naively first. We can run a simple nested loop to find the sum:

Naive Solution Time: O(n²), Space: O(1)

int sum(int x1, int y1, int x2, int y2) {
    int sum = 0;
    for (int i = x1; i <= x2; i++) {
        for (int j = y1; j <= y2; j++) {
            sum += mat[i][j];
        }
    }
    return sum;
}

Problem: The complexity of this code is O(n²). This code will easily fail for higher constraints.

Efficient Approach - 2D Prefix Sum

Let's solve this problem efficiently using 2D prefix sums. We'll store the cumulative sum of the matrix in such a way that cell(i, j) will have cumulative sum of the submatrix having upper left cell(1, 1) and lower right cell(i, j).

Step 1: Building the Prefix Sum Array

Let's have another 2D matrix csum for storing the cumulative sum of the matrix mat.

Formula:

csum[i][j] = mat[i][j] + csum[i-1][j] + csum[i][j-1] - csum[i-1][j-1]

Building Prefix Sum Time: O(n×m), Space: O(n×m)

void calc(int n, int m) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            csum[i][j] = mat[i][j] + csum[i-1][j] + 
                         csum[i][j-1] - csum[i-1][j-1];
        }
    }
}

Step 2: Answering Queries

To find the sum of submatrix from (x1, y1) to (x2, y2), we use the inclusion-exclusion principle:

Query Formula:

sum = csum[x2][y2] - csum[x2][y1-1] - csum[x1-1][y2] + csum[x1-1][y1-1]

Visual Explanation:

1 Take the entire area up to (x2, y2)

2 Subtract the area above our target region

3 Subtract the area to the left of our target region

4 Add back the overlap (subtracted twice)

Query Function Time: O(1), Space: O(1)

int query(int x1, int y1, int x2, int y2) {
    return csum[x2][y2] - csum[x2][y1-1] - 
           csum[x1-1][y2] + csum[x1-1][y1-1];
}

Complete Implementation

Complete C++ Solution Overall: O(n×m + q) where q is number of queries

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

typedef long long int ll;
typedef pair<ll, ll> pll;

const int Max = 2e3 + 10;
const int Mod = 1e9 + 7;
const ll Inf = 1LL << 62;

int mat[Max][Max];
int csum[Max][Max];

void calc(int n, int m) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            csum[i][j] = mat[i][j] + csum[i-1][j] + 
                         csum[i][j-1] - csum[i-1][j-1];
        }
    }
}

int query(int x1, int y1, int x2, int y2) {
    return csum[x2][y2] - csum[x2][y1-1] - 
           csum[x1-1][y2] + csum[x1-1][y1-1];
}

int main(int argc, char const *argv[]) {
    int n, m, q, x1, y1, x2, y2;
    cin >> n >> m >> q;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mat[i][j];
        }
    }
    
    calc(n, m);
    
    while (q--) {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << query(x1, y1, x2, y2) << endl;
    }
    
    return 0;
}

Complexity Analysis

Operation	Time Complexity	Space Complexity
Preprocessing	O(n × m)	O(n × m)
Each Query	O(1)	O(1)
Overall	O(n × m + q)	O(n × m)

Key Takeaways

2D Prefix Sums

Powerful technique for range sum queries in 2D arrays

Inclusion-Exclusion

Essential principle for avoiding double counting

O(1) Queries

After O(n×m) preprocessing, answer queries in constant time

Space-Time Tradeoff

Use extra space to achieve faster query times