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

1. 直接遍历求和

这道题需要我们多次查询数组中某个区间的元素之和。

最容易想到的方法就是直接遍历：先将数组读入，再根据每次查询给出的左右端点，使用 for 循环把区间内的元素逐个累加起来。

需要注意的是，题目中的区间下标从 1 开始，而 Python 和 C++ 的数组下标都从 0 开始。因此，遍历时需要将左端点减去 1。

先来看一下这种最直接的写法。

Python 代码：

Python
import sys

input = lambda: sys.stdin.readline().strip()
n = int(input())
lst = list(map(int, input().split()))
m = int(input())
for i in range(m):
    left, right = map(int, input().split())
    res = 0
    for j in range(left - 1, right):
        res += lst[j]
    print(res)

C++ 代码：

C++
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n = 0;
    cin >> n;
    vector<int> v(n,0);
    for (int i = 0; i < n; i++)cin >> v[i];
    int m = 0;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int left, right,res=0;
        cin >> left>>right;
        for (int i = left - 1; i < right; i++)res += v[i];
        cout << res << endl;
    }
}

这种方法比较直观，实现起来也不复杂。不过，我当时提交测试时发现，Python 版本会超时，而 C++ 版本能够通过。

问题主要出在重复计算上。

每次查询都需要重新遍历对应的区间。如果区间很长，而且查询次数较多，就会反复累加许多已经计算过的元素。

在最坏情况下，一次查询需要遍历整个数组，时间复杂度为 O(n)。如果一共有 m 次查询，那么查询部分的总时间复杂度就会达到 O(n × m)。

既然每次都要重新计算区间和，有没有办法把之前计算过的结果利用起来呢？

2. 使用前缀和优化

可以换个角度考虑这个问题。

假设现在需要求数组中第 3 个到第 7 个元素的和，除了直接累加，还可以这样计算：

前 7 个元素的和 − 前 2 个元素的和

减去前两个元素之后，剩下的正好就是第 3 个到第 7 个元素。

沿着这个思路，如果提前计算并保存前 1 个、前 2 个、前 3 个……元素的累加和，那么后续查询时，就不需要再逐个遍历区间内的元素了。

这就是 前缀和（Prefix Sum） 的基本思想。

我们可以额外创建一个 presum 数组，其中：

  • presum[0] = 0，表示前 0 个元素的和，也就是空前缀。
  • presum[i] 表示原数组前 i 个元素的和。
  • presum[i + 1] = presum[i] + lst[i]，利用前一个位置的结果计算下一个前缀和。

这样一来，对于题目给出的闭区间 [left, right]，就可以直接使用：

presum[right] - presum[left - 1]

得到对应的区间和。

这里的 left 和 right 仍然使用题目给出的一基下标。因为我们在前缀和数组的开头额外放了一个 0，所以计算时不需要再对右端点进行下标转换。

下面是使用前缀和优化后的代码。

C++ 代码：

C++
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n = 0;
    cin >> n;
    vector<int> v(n, 0);
    for (int i = 0; i < n; i++)cin >> v[i];
    vector<int>presum(n + 1, 0);
    for (int i = 0; i < n; i++)presum[i + 1] = presum[i] + v[i];
    int m = 0;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int left, right;
        cin >> left >> right;
        cout << presum[right] - presum[left - 1] << endl;
    }
}

Python 代码：

Python
import sys

input = lambda: sys.stdin.readline().strip()
n = int(input())
lst = list(map(int, input().split()))
presum = [0 for _ in range(n + 1)]
for i in range(n):
    presum[i + 1] = presum[i] + lst[i]
m = int(input())
for i in range(m):
    left, right = map(int, input().split())
    print(presum[right] - presum[left - 1])

与直接遍历相比，前缀和的优势在于：只需要提前计算一次，后续查询就可以直接复用结果。

构建前缀和数组需要遍历一遍原数组，时间复杂度为 O(n)。但完成预处理之后，无论查询的区间有多长，都只需要一次减法，因此单次查询的时间复杂度为 O(1)。

对于 m 次查询，整体时间复杂度也就从原来的最坏 O(n × m) 降到了 O(n + m)，代价是额外使用 O(n) 的空间保存前缀和数组。

这也是前缀和适合处理多次静态区间求和查询的原因：通过提前保存累加结果，避免每次查询都重复计算相同的元素。

谢谢你读到这里。 ✧

聊两句

评论审核后显示

有疑问、补充，或者想交流一下，都可以写在这里。

评论区将在滚动到这里时加载。