new_【玩转C++，一起加油鸭~】系列 -- 前缀和

元豪

版权属于zhangjinxuan。

前缀和

大家好，我是 zhangjinxuan，欢迎收看我们的 玩转C++，一起加油鸭~ 系列

今天，我来为大家讲解一道题，让大家练习

题目描述
给一个数列 a-1,a_2,…,a_n和 m个询问。

每次询问给出两个数 l,r，求 a_l+a_(l+1)+⋯+a_r的值。

也就是 a 中 l 到 r 这一段的和
输入格式
第一行两个整数 n,m。

接下来一行 n 个整数 a1,a2,…,an。

接下来 m行，每行两个整数 l,r。

输出格式
输出 m行，每行一个整数表示答案。
样例输入

1. 5 5
   
2. 7 6 4 7 4
   
3. 2 5
   
4. 1 3
   
5. 3 5
   
6. 1 2
   
7. 2 4

复制代码

样例输出

1. 21
   
2. 17
   
3. 15
   
4. 13
   
5. 17

复制代码

数据规模
对于 100% 的数据，保证 1≤n,m≤10^5,1≤ai≤10^9,1≤l≤r≤n。

本题并非原创，转载于：http://oj.daimayuan.top/course/27/problem/58

                               
登录/注册后可看大图

图一时查看答案，你将失去一次锻炼的机会！

                               
登录/注册后可看大图

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

拓展
请用后缀和的做法再来做一做这道题，也就是说，s_i 要等于 a_i + a_(i+1) + a_(i+2) + ... + a_n

奖励版
根据实际情况来奖励对应的积分~

	名字	链接	奖励
第一名	希望大家踊跃回答！
第二名
第三名

元豪

@zhangjinxuan @sfqxx @歌者文明清理员 @学习编程中的Ben @liuhongrun2022

sfqxx

顶