二维前缀和

· · 个人记录

前言：

我们都知道，前缀和的应用是非常广泛的。他可以维护一个静态序列前 i (1≤i≤n) 个数的和，从而可以在 O(1) 的时间复杂度求出序列里任意一个区间的和。

但是，上面提到的仅仅是一个一维序列的前缀和，如果是一个二维数组呢？这里就要引入二维前缀和了。

例题：

先看这样一个题：

给你一个二维数组，每次查找任意一个子矩阵的元素之和。

如果直接去暴力求的话，每次查找的时间复杂度最坏为 O(n^2) 如果数据范围很大，一定会 TLE，这里就要引入二维前缀和的知识了。

算法：

既然叫前缀和，那么就得有两个操作：

  1. 预处理出前任意个数的和。

下面就分别实现这两个操作。

预处理：

很多人可以一开始想：直接将左上角到每个点间的元素加一遍，不就预处理出前缀和了吗。但如果这样做，时间复杂度为 O(n^4)，无法接受。

其实这个是可以递推计算的。

设 a_{i,j} 表示矩阵中左上角到 (i,j) 间的数字之和，也就是二位前缀和，那么，在求 a_{i,j} 前，就已经求出了 a_{i-1,j}，a_{i,j-1}，a_{i-1,j-1} 的值，就可以用容斥原理。 如果还是看不出来，可以再看一看一张图。 图有点丑qwq 整个紫色框中，也就是要求的和可以用 i,j 加上蓝色和黄色的部分，也就是 a_{i-1,j} 和 a_{i,j-1}。但是，绿色的部分，也就是 a_{i-1,j-1} 多算了一次，所以要减掉。

因此，对于 a_{i,j}，它的值就是 x_{i,j}+a_{i-1,j}+a_{i,j-1}+a_{i-1,j-1}（x 为矩阵元素的值）

查询：

对于查询 (x1,y1) 至 (x2,y2) 间元素的和时，同样也可以用容斥。

具体的，对于下面这个图

红色为要查询的部分，其他的与上文意思相近，可根据红色字体理解。

与计算类似，可以用 a_{x2,y2} 减去多余的 a_{x1-1,y2} 和 a_{x2,y1-1}。但是由于重叠的 a_{x1-1,y1-1} 被多减了一次，所以要加回去。

总结一下，结果就是 a_{x2,y2}-a_{x1-1,y2}-a_{x2,y1-1}+a_{x1-1,y1-1}。

代码：

这里简单给一下二维前缀和的部分代码，以供参考。

预处理代码：

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=n;j++)
    {
        int x;
        scanf("%d",&x);
        a[i][j]=x+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    }
}

查询代码：

int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int ans=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
printf("%d\n",ans);

后记：

以上就是我对二位前缀和的简单介绍。如果想运用一下可以做一做这道题，希望这篇博客能对你有帮助