题目链接: 求区间和

如果就按题意,我们简单的想的话,那就是这个题读取完数据,然后再读区间,确定起始索引和终止索引.然后用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)复杂度的一个求区间和.

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