Acwing基础课每日一题 第十一天 795-简单-前缀和

目录

前言

作者简介

题目描述

思路解析

结语


原题链接:795-简单-前缀和

前言

算法是考研和实习找工作进大厂的必备工具,为了23考研以及日后进大厂,开始学习算法!

作者简介

大家好,我是977,一个正在慢慢进步的程序猿小白,很高兴能在这里遇见大家,每天一点点成长,一起早日成为大佬!!!

算法基础课共106题

这是我的第11/106题

题目描述

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

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

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

输入格式

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

第二行包含 n 个整数,表示整数数列。

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

输出格式

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

数据范围

1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000

输入样例

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

输入样例

3
6
10

思路解析:

算法:

时间复杂度:O(nlog(n))

解题思路:

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化

    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]); // 区间和的计算
    }

    return 0;
}

结语

学习贵在坚持,Acwing算法基础课,每日一题

期待各位的关注和监督

上一篇:AcWing刷题——逆序对的数量(经典逆序对)


下一篇:0x02递推与递归例题