设二维数组A的大小为m*n,行下表的范围为[1,m]列下标的范围为[1,n].

数组P是A的前缀和数组，等价于P中的每个元素P[i][j]:

• 如果i和j均大于0，那么P[i][j]表示A中以（1，1）为左上角，（i,j）为右下角的矩形区域的元素之和；
• 如果i和j中至少有一个等于0，那么P[i][j]也等于0;

数组P可以帮助我们在O（1）的时间内求出任意一个矩形区域的元素之和。具体地，设我们需要求和的矩形区域的左上角为（x1,y1）,右下角为（x2,y2），则该矩形区域的元素之和可以表示为：

1
2

sum = A[x1...x2][y1...y2]
    = P[x2][y2]-P[x1-1][y2]-P[x2][y1-1]+P[x1-1][y1-1]

其正确性可以通过容斥远离得出。以下图为例，当A的大小为8*5，需要求和的矩形区域（深绿色部分）的左上角为（3，2），右下角为（5，5）时，该矩形区域的元素之和为

1

P[5][5]-P[2][5]-P[5][1]+P[2][1]

那么如何得到数组P（数组P是A的前缀数组也就是开头讲的）呢？我们按照行优先的顺序依次计算数组P中的每个元素，即当我们在计算P[i][j]时，数组P的前i-1行，以及第i行的前j-1各元素都已经计算完成。此时我们可以考虑（i,j）这个1*1的矩形区域，根据上面的等式，有：

1

A[i][j] = P[i][j] - P[i - 1][j] - P[i][j - 1] + P[i - 1][j - 1]

A[i][j]是：左上角第一个元素到A[i][j]包含的矩形区域的和

由于等式中的A[i][j],P[i-1][j],P[i][j-1]和P[i-1][j-1]均已知我们可以通过

1

P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + A[i][j]

在O（1）的时间计算出P[i][j]。因此按照行优先的顺序，我们可以在O（MN）的时间得到数组P。在此之后，我们就可以很方便的在O（1）时间能求出任意一个矩形区域的元素之和了。

注意事项：

在大部分语言中，数组下标是从 0 而不是 1 开始，在实际的代码编写过程中需要考虑这一情况。

参考文献

力扣官方题解

赏

谢谢你请我吃糖果

微信