算法进阶：一维前缀和原理与实战

问题背景

在算法竞赛和实际开发中，我们经常遇到需要频繁查询数组区间和的场景。如果直接遍历求和，效率往往难以满足要求。今天我们来聊聊如何高效解决这类问题——一维前缀和。

核心思路

前缀和的本质是空间换时间。通过预处理，将多次区间查询的时间复杂度从 $O(N)$ 降低到 $O(1)$。

为什么不用暴力？

假设数组长度为 $N$，查询次数为 $m$。暴力解法每次遍历区间，总复杂度约为 $O(m \times N)$。当 $N$ 和 $m$ 都达到 $10^5$ 级别时，运算量高达 $10^{10}$，必然超时。

前缀和怎么做？

我们需要构建一个辅助数组 dp，其中 dp[i] 表示原数组 arr 前 i 个元素的和。

1. 预处理：创建一个大小为 $N+1$ 的数组。之所以多一位，是因为 dp[0] 设为 0，方便处理边界情况，避免下标越界。 递推公式：dp[i] = dp[i-1] + arr[i]
2. 查询：对于区间 [l, r]，其和等于 dp[r] - dp[l-1]。

代码实现

下面是一个标准的 C++ 实现示例，展示了如何构建前缀和数组并进行查询。

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

int main() {
    // 初始化数组
    int n = 5;
    vector<int> arr = {1, 2, 3, 4, 5};
    
    // 构建前缀和数组，大小为 n+1
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + arr[i - 1];
    }

    // 查询区间 [1, 3] 的和
     l = , r = ;
     sum = dp[r] - dp[l - ];
    cout <<  << l <<  << r <<  << sum << endl;

     ;
}