算法基础：一维与二维前缀和详解 | 极客日志

C++算法

算法基础：一维与二维前缀和详解

前缀和是一种通过预处理优化区间查询的经典算法思想，核心在于用空间换取时间。本文详细讲解了一维前缀和的构建与查询方法，解决了 O(n*m) 暴力枚举的性能瓶颈。进一步扩展到二维前缀和，推导了矩形区域求和公式。结合最大子段和与激光炸弹实例，展示了如何利用前缀和数组快速计算特定范围内的数值总和，适用于各类算法竞赛及工程场景中的高频区间统计问题。

flc发布于 2026/1/60 浏览

算法基础：一维与二维前缀和详解

算法基础：前缀和实战

前缀和的核心思想是预处理。它能在暴力枚举的过程中快速查询到结果，相当于是对枚举的优化，是经典的用空间换时间的做法。

一维前缀和

思路解析

直观来看，暴力解法每次询问直接遍历区间 [l, r]，复杂度是 O(n*m)，在数据量大时显然不可接受。

由于我们需要计算的是连续区间的和，可以利用前缀数组来加速。假设定义 f[i] 为下标从 0 到 i 的数字之和（即前缀和），那么任意区间 [x, y] 的和就可以通过 f[y] - f[x-1] 快速得到。

这里有个细节需要注意：题目给出的是闭区间 [x, y]，f[x] 包含了 v[x] 这个数，所以减去 f[x-1] 才能正好去掉 x 之前的部分，保留 x 到 y 的范围。

文章配图

参考实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    // 使用 long long 防止溢出，多开一位方便处理边界
    vector<long long> f(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        long long num;
        cin >> num;
        f[i] = f[i - 1] + num; // 预处理前缀和数组
    }
    
    while (m--) {
        int a, b;
        cin >> a >> b;
        cout << f[b] - f[a - 1] << endl;
    }
    return ;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<long long> f(n + 1);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        f[i] = f[i - 1] + x;
    }
    
    long long ret = -1e20;      // 初始化为极小值
    long long prevmin = 0;      // 记录当前遇到的最小前缀和
    
    for (int i = 1; i <= n; i++) {
        ret = max(ret, f[i] - prevmin); // 更新最大子段和
        prevmin = min(prevmin, f[i]);   // 更新最小前缀和
    }
    
    cout << ret << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    
    // 注意维度大小，通常根据题目限制设定
    vector<vector<long long>> f(a + 1, vector<long long>(b + 1, 0));
    
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            int num;
            cin >> num;
            // 二维前缀和递推公式
            f[i][j] = f[i][j - 1] + f[i - 1][j] + num - f[i - 1][j - 1];
        }
    }
    
    while (c--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // 矩形区域求和
        cout << f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 5005;

int main() {
    int n, m;
    cin >> n >> m;
    
    // 使用全局或大数组存储价值，初始化为 0
    vector<vector<int>> v(MAX, vector<int>(MAX, 0));
    
    for (int i = 0; i < n; i++) {
        int x, y, value;
        cin >> x >> y >> value;
        // 坐标转 1-based，避免处理 0 边界
        v[x + 1][y + 1] += value;
    }
    
    // 构建二维前缀和
    for (int i = 1; i < MAX; i++) {
        for (int j = 1; j < MAX; j++) {
            v[i][j] = v[i][j] + v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
        }
    }
    
    int ret = 0;
    // 处理 m 大于地图尺寸的情况
    int r = min(m, MAX - 1);
    
    for (int i = r; i < MAX; i++) {
        for (int j = r; j < MAX; j++) {
            // 计算 m*m 区域内的价值和
            int sum = v[i][j] - v[i - r][j] - v[i][j - r] + v[i - r][j - r];
            if (sum > ret) {
                ret = sum;
            }
        }
    }
    
    cout << ret << endl;
    return 0;
}