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

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

最直接的做法是读入数组，再逐次读取查询区间，用 for 循环累加左右端点之间的元素，得到这一段的和。

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++ 代码如下：

#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++ 写法可以通过，但仍有优化空间。例如区间 [3,7] 的和，可以由区间 [0,7] 的和减去区间 [0,2] 的和得到。提前保存 [0,1]、[0,2]、[0,3]……这些前缀区间的和，每次查询就只需做一次减法，时间复杂度为 O(1)。下面的代码用 presum[0]=0 作为空前缀，题目的一基闭区间 [left,right] 对应 presum[right]-presum[left-1]。

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 代码如下：

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])