算法基础课题解合集

什么是二维前缀和

二位前缀和$S_{i,j}$ 表示从 $A_{1,1}$ 到 $A_{i,j}$ 的数的和。

那如何快速初始化出二维前缀和呢？

我们可以画一个图。

所以公式就是 $S_{i, j} = S_{i - 1, j} + S_{i, j - 1} - S_{i - 1, j - 1} + A_{i, j}$

二维前缀和的应用

如题，求 $A_{x1, y1}$ 到 $A_{x2, y2}$ 中所有数的和。

那么我们还是可以画个图分析一下。

所以公式就是 $S_{x2,y2} - S_{x1 - 1, y2} - S_{x2, y1 - 1} + S_{x1 - 1, y1 - 1}$

代码

#include <iostream>

using namespace std;

const int N = 1005;
int n, m, q;
int a[N][N], s[N][N];

int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> a[i][j];
    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] + a[i][j];
    while (q --)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

好了，这篇题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$