前缀和

一维前缀和

给定一个数组，求出指定区间的和。

#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int a[N],s[N];
int n;

int main() {
    cout << "输入数组大小:";
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i < n; ++i) {
        s[i] = s[i - 1] + a[i];
    }
    cout << endl;

    // 计算区间 [l, r] 的和
    int l, r;
    cout<<"输入区间的左右边界:";
    cin >> l >> r;
    int sum = s[r] - s[l - 1];

    cout << "区间 [" << l << ", " << r << "] 的和为: " << sum << endl;

    return 0;
}

测试结果如下：

二维前缀和

给定一个二维数组，求出指定矩形的和。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 1010;
int s[N][N], a[N][N];
int main() {
    int n, m, q;
    cout << "输入矩阵的行数、列数、询问次数:";
    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, x2, y1, y2;
        cout << "输入两个点位:";
        cin >> x1 >> y1 >> x2 >> y2;
        printf("结果是：%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 -1]);
    }
    return 0;
}

测试结果如下：

评论