前缀和（prefix sum）

Posted on

前缀和是一种很常见的数据结构，在 leetcode 上面也有相应的题目，如（523，1292）。我们利用前缀和可以很容易快速的求出一块区域的值。我们分一维数组的前缀和和二维数组的前缀和来介绍。

一维数组的前缀和

在一维数组中，某一点的前缀和表示从数组的起始点到这一点的所有元素加在一起的值。如下例：

1
2
a = [6, 3, 7, 2, 4]
prefix_sum = [6, 9, 16, 18, 22]

利用前缀我们可以很快的算出 a[1:3] 的大小为 prefix_sum[3 - 1] - prefix_sum[1 - 1] = 10。很容易看出公式为 a[i: j] = prefix_sum[j - 1] - prefix_sum[i - 1]。

二维数组的前缀和

一维数组的前缀和可以算出其中一段的和，二维数组就可以算出一块区域的和。如下例：

1
2
3
4
a = [[5, 1, 3, 4],
     [1, 4, 7, 2],
     [5, 3, 6, 1],
     [2, 4, 3, 5]]

这里的 prefix_sum[i][j] 我们这样定义，如果 i = 0 或者 j = 0， 那么prefix_sum[i][j] = 0；如果 i != 0 且 j != 0，那么 prefix_sum[i][j] = prefix_sum[i][j - 1] + prefix_sum[i - 1][j] - prefix_sum[i - 1][j - 1] + a[i][j]。令 M 维行数，N 为列数，通过上述公式我们在 O(MxN) 的时间里就能得到 (M + 1) x (N + 1) 个前缀和。有了这个前缀和，如下所示：

1
2
3
4
5
P = [[0,  0,  0,  0,  0],
     [0,  5,  6,  9, 13],
     [0,  6, 11, 21, 27]
     [0, 11, 19, 35, 42],
     [0, 13, 25, 44, 56]]

如果我们想知道以（1，1) 为左上定点，（3， 2）为右下顶点的矩形的和，我们可以计算利用公式 ans = P[x2 + 1][y2 + 1] - P[x1 + 1][y2 + 1] - P[x2 + 1][y1 + 1] + P[x1][y11]来计算，得到ans = P[3 + 1][2 + 1] - P[0 + 1][2 + 1] - P[3 + 1][0 + 1] + P[0 + 1][0 + 1] = 44 - 9 - 13 + 5 = 27。

0%