题目描述

原题

题目大意&链接

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

输入输出样例：
输入：

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

输出：

3
6
10

详情：ac_795前缀和

解题思路

前缀和需要注意1点。

  1. 需要明确 res[i] 表示前i个元素的和，因此： 
    for(int i = 1; i <= n; i++) 
    {
        scanf("%d", &q[i]);
        res[i] = res[i-1] + q[i];
    }

完整代码

#include<iostream>

using namespace std;

const int N = 1e6 + 10;
int n, m;
int q[N];
int res[N] = {0}; // res[i]表示前i个元素的和（从1开始）

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) 
    {
        scanf("%d", &q[i]);
        res[i] = res[i-1] + q[i];
    }
    
    while(m--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", res[r] - res[l-1]);
    }
    return 0;
}

时间和空间复杂度

时间复杂度：O(n + m) 输入时遍历 n 个元素数组 res + m 次询问
空间复杂度：O(n)