前缀和算法详解：快速求解区间和的利器（含C++板子）

前缀和算法详解：快速求解区间和的利器

引言

在算法和数据处理中，区间求和是常见的基础操作。传统暴力解法每次查询需要遍历区间元素，当面对海量查询时效率极低。本文将介绍一种名为前缀和的高效算法，它能将区间求和的时间复杂度降至O(1)，是处理静态数组区间求和问题的终极利器。

一、什么是前缀和？

1.1 核心思想

前缀和（Prefix Sum）通过预处理构建一个辅助数组，其中每个元素存储原数组从起始位置到当前位置的元素之和。通过巧妙的数学关系，我们可以将区间求和转换为简单的差值运算。

1.2 重要公式

前缀和数组构建：
sum[i] = sum[i-1] + a[i]
区间和计算（闭区间[l, r]）：
sum[r] - sum[l-1]

二、算法实现步骤

2.1 预处理阶段

创建与原数组等长的前缀和数组
初始化sum[0] = 0（索引从1开始更易处理边界）

递推计算每个位置的前缀和：

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

2.2 查询阶段

int getSum(int l, int r) {
    return sum[r] - sum[l-1];
}

三、实战演示

3.1 示例分析

假设原数组：
a = [0, 3, 1, 2, 5]（索引1-4）

构建前缀和数组：
sum = [0, 3, 4, 6, 11]

计算区间[2,4]的和：
sum[4] - sum[1] = 11 - 3 = 8
对应实际元素：1 + 2 + 5 = 8

3.2 完整代码

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

typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10;

int main() {
    int n, q;
    int a[N], s[N];
    cin >> n >> q;
    // vector<int> a(n + 1), s(n + 1);

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

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

四、算法特性

特性	说明
时间复杂度	预处理O(n)，查询O(1)
空间复杂度	O(n)
适用场景	静态数组的频繁区间求和
不适用场景	需要动态修改数组元素的场景

五、应用场景

频繁查询固定数组的区间和
二维矩阵的子矩阵求和（需二维前缀和）
配合哈希表解决特定问题（如寻找和为k的子数组）
数据统计中的滑动窗口预处理

六、注意事项

索引处理：建议从1开始存储数据，避免复杂的边界判断
数值溢出：使用足够大的数据类型（如long long）
初始化：确保sum[0]正确初始化为0
区间有效性：需验证查询参数的合法性（1 ≤ l ≤ r ≤ n）

七、总结

前缀和算法通过空间换时间的策略，将看似复杂的区间求和问题转化为简单的数学运算。其核心在于：

预处理建立全局视角
利用差值运算快速定位区间
索引的巧妙设计简化计算

掌握前缀和不仅能提升算法效率，更能培养重要的预处理思维，为后续学习更复杂的算法（如差分数组、动态规划）打下坚实基础。

拓展思考：如何将前缀和思想应用到二维数组的子矩阵求和问题中？欢迎在评论区分享你的见解！

秒客网