Vocabulary - 2D Prefix Sum

A 2D prefix sum array stores cumulative sums over rectangles.

For matrix $mat$: $prefix[i][j] = \sum_{r=0}^{i-1} \sum_{c=0}^{j-1} mat[r][c]$ You get the sum of all elements in the rectangle with top-left $(0, 0)$ and bottom-right $(i-1, j-1)$.

Building this array takes $O(nm)$ time for an $n \times m$ matrix. After that, any submatrix sum is $O(1)$.