Submatrix Sum in O(1)

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

Problem

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

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
mat	Col 1	Col 2	Col 3	Col 4	Col 5	Col 6

You need to do some queries, in every queries 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, we need to find the sum of sub-matrix having cells (2, 3) and (4, 5).

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
mat	Col 1	Col 2	Col 3	Col 4	Col 5	Col 6

Solution

Naive Approach

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

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;
}

But the complexity of this code is O(n2). This code will easily fail for higher constraints.

Efficient Approach

Let’s solve this problem efficiently.

Let’s store the cumulative sum of the matrix. We will store the cumulative sum in such a way that the cell(i, j) will have cumulative sum of the submatrix having upper left cell(1, 1) and lower right cell(i, j). How will we do that?

Let’s have another 2D matrix csum for storing the cumulative sum of the matrix mat.
Then csum[1][1] will be equal to mat[1][1] as cell(1,1) is the only cell of the submatrix having upper left cell(1, 1) and lower right cell(1, 1).

So, csum[1][1] = mat[1][1] = 3.

csum[1][2] will have the value equal to mat[1][2] + csum[1][1] as the cumulative sum upto cell(1, 2) will have the sum of every cells of the submatrix having upper left cell(1, 1) and lower right cell(1, 2). So that, by adding csum[1][1] with mat[1][2], we will get csum[1][2] which is the cumulative sum of cell(1, 1) and cell(1, 2).

So, csum[1][2] = csum[1][1] + mat[1][2] = 3 + 5 = 8.

Similarly csum[1][3] = csum[1][2] + mat[1][3] = 8 + 1 = 9 and so on. By doing the same for the other cells of row 1, we will get the cumulative sum of raw 1.

Row 1	3	8	9	25	33	46
Row 2
Row 3
Row 4
Row 5
csum	Col 1	Col 2	Col 3	Col 4	Col 5	Col 6

Now for the cell(2, 1). The csum[2][1] will be the sum of csum[1][1] and mat[2][1].

So, csum[2][1] = csum[1][1] + mat[2][1] = 3 + 12 = 15.

Here comes a bit complex calculation. For the cell(2, 2), csum[2][2] should contain the sum of those cells of mat matrix: (1, 1), (1, 2) (2, 1) and (2, 2).

Sum of cell(2, 2) is mat[2][2]
We can get the sum of cell(1, 1) and cell(1, 2) from csum[1][2].
And the sum of cell(1, 1) and cell(2, 1) from csum[2][1].
As we can see that cell(1, 1) is counted twice, we can subtract csum[1][1] so that it will be counted only once.

So finally, csum[2][2] = mat[2][2] + csum[1][2] + csum[2][1] - csum[1][1] = 2 + 8 + 15 - 3 = 22

We caught the pattern! We will store the cumulative sum for mat matrix as following:

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

The code for calculating cumulative sum is following:

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];
                }
        }
}

The final cumulative array will look like as following:

Row 1	3	8	9	25	33	46
Row 2	15	22	36	61	80	99
Row 3	22	39	59	96	119	145
Row 4	33	56	93	134	164	208
Row 5	41	78	122	171	213	260
csum	Col 1	Col 2	Col 3	Col 4	Col 5	Col 6

Let’s now get back to the query part. Following is the mat matrix and we need the sum of the highlighted submatrix:

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
mat	Col 1	Col 2	Col 3	Col 4	Col 5	Col 6

The upper left of the submatrix is (2, 3) and the lower right cell is (4, 5). We can get the sum of that submatrix by doing the following:

Firstly, get the cumulative sum of the submatrix [(1, 1), (4, 5)] which is csum[4][5].
Now, we need to subtract the sum of other cells from csum[4][5] that are not in the submatrix [(2, 3), (4, 5)] but in the submatrix [(1, 1), (4, 5)]. Let color the cells that need to be subtracted.

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
mat	Col 1	Col 2	Col 3	Col 4	Col 5	Col 6

We will subtract csum[4, 2] so that the sum of cells (1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2), (4, 1) and (4, 2) are subtracted.

Then we will subtract csum[1, 5] so that the sum of cells (1, 1), (1, 2), (1, 3), (1, 4) and (1, 5) are subtracted.

As we see the sum of cells (1, 1) and (1, 2) is subtracted twice, we will now add them again so that every cell is subtracted only once. We can add them by adding csum[1, 2].

We got it! The sum of submatrix [(2, 3), (4, 5)] = csum[4][5] - csum[4][2] - csum[1][5] + csum[1][2] = 164 - 56 - 33 + 8 = 83

So if (x1, y1) is upper left cell and (x2, y2) is the lower right cell of the submatrix, the sum of that submatrix is equal to csum[x2][y2] - csum[x2][y1 - 1] - csum[x1 - 1][y2] + csum[x1 - 1][y1 - 1].

Here is the final code:

#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;
}

You can try to solve this problem for practice.