题目描述

输入一个长度为n的整数序列。

接下来再输入m个询问，每个询问输入一对l, r。

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

样例

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

3
6
10

算法

(暴力枚举)

1. 这道题很简单，说一点。就是i从0开始还是1开始，一开始用的1开始，也是y总教的，但是这几天做leetcode周赛，数组都是vector呈现的，不太会改，让给好的vector数组从1开始，所以学会从0开始枚举也挺有必要的，下面给出的就是从0开始枚举的。(如果有大佬知道vector怎么改成从1开始，麻烦说一下hh)

时间复杂度

$O(n)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int a[N], s[N];

int main()
{
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i ++) cin >> a[i];

    for(int i = 0; i < n; i ++) s[i + 1] = s[i] + a[i];

    while(m --)
    {
        int l, r;
        cin >> l >> r;
        printf("%d\n", s[r] - s[l - 1]);
    }

    return 0;
}