前缀和

一维前缀和

前缀和可以简单理解为「数列的前项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。

利用前缀和可以在常数时间复杂度中查询区间和

例题，P8218 【深进1.例1】求区间和

题意，m 次询问，每次输出 [l, r] 的区间和

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], n, m;
long long s[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

    cin >> m;
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%lld\n", s[r] - s[l - 1]);
    }

    return 0;
}

二维前缀和

例题，P1719 最大加权矩形

题意，输入最大子矩阵和，n <= 120

#include <bits/stdc++.h>

using namespace std;

const int N = 150;

int a[N][N], s[N][N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1;  j <= n; j++) 
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

    int ret = -2e9;
    for (int xa = 1; xa <= n; xa++)
        for (int ya = 1; ya <= n; ya++)
            for (int xb = xa; xb <= n; xb++)
                for (int yb = ya; yb <= n; yb++) 
                    ret = max(ret, s[xb][yb] - s[xa - 1][yb] - s[xb][ya - 1] + s[xa - 1][ya - 1]);


    cout << ret << '\n';

    return 0;
}

总结

下标，都必须从 1 开始，否则，代码不好写