知识点：前缀和

输入一个长度为 n 的整数序列，接下来再输入 m 个询问，1≤n,m≤100000。

每个询问输入一对 l,r，1≤l≤r≤n。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式：

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数数列，−1000≤数列中元素的值≤1000。

接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式：

共 m 行，每行输出一个询问的结果。

输入样例：

1
2
3
4
5
5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例：

1
2
3
3
6
10

思路

题目已经给了提示啦：前缀和

如果暴力计算，每次都遍历区间[l,r]，复杂度最坏是O(mn)

使用前缀和数组pre，记录pre[i]记录前i个数的和，复杂度最坏是O(m)

知识点：一维数组前缀和

上次CSP的第二题，可以使用二维数组前缀和优化，才能满分。邻域均值

代码

如下是前缀和计算，最坏复杂度O(m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> pre(n + 1); //前缀和，pre[i]表示前i个数的和
    for(int i = 1; i <= n; i++) {
        int id;
        cin >> id;//就不使用数组记录id了，省点空间
        pre[i] = pre[i - 1] + id;//前i个数的和是前(i-1)个数的和加上第i个数
        /**
        * 若是二维数组，则pre[a][b]表示前a行和b列共a*b个数的和
        * pre[a][b]=pre[a-1][b]+pre[a][b-1]-pre[a-1][b-1]+id
        */
    }
    while(m--) {
        int a, b;
        cin >> a >> b;
        cout << pre[b] - pre[a - 1] << endl;
    }
    return 0;
}

如下是暴力计算，最坏复杂度O(mn)，本题也不会超时（不太合理）。可对比下两种方法的耗时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> ve;
    for(int i = 1; i <= n; i++) {
        int id;
        cin >> id;
        ve.push_back(id);
    }
    while(m--) {
        int a, b;
        cin >> a >> b;
        int sum = 0;
        while(a <= b) {
            sum += ve[a - 1];
            a++;
        }
        cout << sum << endl;
    }
    return 0;
}