本篇推文共計(jì)2000個字，閱讀時間約3分鐘。

題目描述：

給定一個二維矩陣，

計(jì)算其子矩形范圍內(nèi)元素的總和，

該子矩陣的

左上角為(row1,col1)，右下角為(row2,col2)

如下矩陣所示：

下圖中間的子矩陣

左上角(row1,col1)=(1,1)，

右下角(row2,col2)=(3,3)，

該子矩形區(qū)域內(nèi)元素的總和為10。

這道題是一維前綴和的升級，可以稱為二維前綴和。

之前的一維前綴和分析可以查看這篇文章

【一天一道Leetcode】數(shù)組不可變

我們先來分析一下這道題

假設(shè)m和n分別是矩陣matrix的行數(shù)和列數(shù)。

當(dāng)0≤i<m且0≤j<n時，

f(i,j)為矩陣matrix

以(i,j)為右下角標(biāo)的子矩陣的元素之和。

當(dāng)i=0或j=0時，

計(jì)算f(i,j)只需要對矩陣matrix的最上邊的行或最左邊的列分別計(jì)算前綴和即可。

即如下圖所示，

f(i,j)為第一行或第一列的元素區(qū)域累加數(shù)值。

當(dāng)i和j都大于0時，我們要計(jì)算f(i,j)

如下圖所示，計(jì)算矩陣matrix的前綴和f(2,2)

f(2,2)=紫色區(qū)域+橙色區(qū)域-綠色區(qū)域+matrix[2,2]

f(2,2)=f(1,2)+f(2,1)-f(1,1)+matrix[2,2]

即：

f(i,j)=f(i-1,j)+f(i,j-1)-f(i-1,j-1)+matrix[i,j]

根據(jù)題意

當(dāng)row1=0且col1=0時，

sumRange(row1, col1, row2, col2)=f(row2, col2)

當(dāng)row1≠0，col1≠0，row1<=row2，col1<=col2時

由一維前綴和的公式可知

數(shù)組（i,j）范圍內(nèi)的元素和為

sumRange(i,j)= presums[j+1]-presums[i]

二維矩陣的（row1, col1, row2, col2）區(qū)域元素和為

sumRange(row1, col1, row2, col2)=
f(row2, col2)-f(row1-1,col2)-f(row2,col1-1)+f(row1-1,col1-1)

用圖像來直觀說明，如下圖矩陣：

我們需要求藍(lán)色方框塊的元素和

也即是矩陣中(1,1)到(2,2)區(qū)域的元素和

f(1,1,2,2)=f(2,2)-f(0,2)-f(2,0)+f(0,0)

f(2,2)代表綠色方框內(nèi)的元素和

f(0,2)代表紫色方框內(nèi)的元素和

f(2,0)代表橙色方框內(nèi)的元素和

由于f(2,2)-f(0,2)-f(2,0)多減掉了一個f(0,0)

最后需要加上f(0,0)

則最后公式為

f(1,1,2,2)=f(2,2)-f(0,2)-f(2,0)+f(0,0)

我們的代碼表示為：

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            pass
        else:
            m, n = len(matrix), len(matrix[0]) 
            self.sums = [[0] * (n + 1) for i in range(m + 1)]
            _sums = self.sums

            for i in range(m):
                for j in range(n):
                    _sums[i+1][j+1] = _sums[i][j+1]+_sums[i+1][j]-_sums[i][j]+matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        _sums = self.sums
        return _sums[row2+1][col2+1]-_sums[row1][col2+1]-_sums[row2+1][col1]+_sums[row1][col1]