二维前缀和

作用：当程序需要大量计算数列中某一段数字之和的时候，可以通过前缀和算法优化查询的时间复杂度。

预处理：O(n*m)

查询：O(1)

原理：

紫色面积是指(1,1)(1,1)左上角到(i,j−1)(i,j−1)右下角的矩形面积, 绿色面积是指(1,1)(1,1)左上角到(i−1,j)(i−1,j)右下角的矩形面积。每一个颜色的矩形面积都代表了它所包围元素的和。

从图中我们很容易看出，整个外围蓝色矩形面积s[i][j]s[i][j] = 绿色面积[i−1][j][i−1][j] + 紫色面积s[i][j−1]s[i][j−1] - 重复加的红色的面积s[i−1][j−1]s[i−1][j−1] + 小方块的面积a[i][j]a[i][j];

因此得出二维前缀和预处理公式

s[i][j]=s[i−1][j]+s[i][j−1]+a[i][j]−s[i−1][j−1]s[i][j]=s[i−1][j]+s[i][j−1]+a[i][j]−s[i−1][j−1]

现在要求求以(x1,y1)(x1,y1)为左上角和以(x2,y2)(x2,y2)为右下角的矩阵的元素的和。

紫色面积是指(1,1)(1,1)左上角到(x1−1,y2)(x1−1,y2)右下角的矩形面积 ，黄色面积是指(1,1)(1,1)左上角到(x2,y1−1)(x2,y1−1)右下角的矩形面积；

绿色矩形的面积 = 整个外围面积s[x2,y2]s[x2,y2] - 黄色面积s[x2,y1−1]s[x2,y1−1] - 紫色面积s[x1−1,y2]s[x1−1,y2] + 重复减去的红色面积 s[x1−1,y1−1]s[x1−1,y1−1]

因此二维前缀和的结论为：

以(x1,y1)(x1,y1)为左上角，(x2,y2)(x2,y2)为右下角的子矩阵的和为： s[x2,y2]−s[x1−1,y2]−s[x2,y1−1]+s[x1−1,y1−1]s[x2,y2]−s[x1−1,y2]−s[x2,y1−1]+s[x1−1,y1−1]

for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];  //二维前缀和预处理公式
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); //二维前缀和查询区间的计算