...
| 代码块 |
|---|
2 4 6 8 10 12 14 16 18 20 2 4 8 16 32 64 128 256 512 1024 |
二维前缀和
将前缀和的概念扩展到二维数组，比如对于数组grid，点(x,y)的前缀和就是从(0,0)到(x,y)定义的矩形的和，它的求和公式为：
sum[x][y] =grid[x][y] + sum[x][y-1] + sum[x-1][y] - sum[x-1][y-1]
示意图如下：
求(x1,y1)和(x2,y2)构成的矩形的和，公式为：
area = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]
示意图如下：
