Acwing基础课每日一题 第十一天 795-简单-前缀和
2022/1/10 23:04:04
本文主要是介绍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基础课每日一题 第十一天 795-简单-前缀和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验
- 2024-05-29AutoMQ 对象存储数据高效组织的秘密: Compaction
- 2024-05-29活动预告|来 GIAC 大会听大数据降本利器:AutoMQ 基于云原生重新设计的 Kafka