前缀和(板子题)

举报
irrational 发表于 2022/01/18 00:25:52 2022/01/18
【摘要】 // 一维前缀和 // S[i] = a[1] + a[2] + ... a[i] // a[l] + ... + a[r] = S[r] - S[l - 1]   输入一个长度为n的整数序列。 接下来再输入m个询问,每个询问输入一对l, r。 对于每个询问,输出原序列中从第Ⅰ个数到第r个数的和。 输入格式 第一...

// 一维前缀和
// S[i] = a[1] + a[2] + ... a[i]
// a[l] + ... + a[r] = S[r] - S[l - 1]

 

输入一个长度为n的整数序列。
接下来再输入m个询问,每个询问输入一对l, r。
对于每个询问,输出原序列中从第Ⅰ个数到第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
  
 

 


      #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;
      }
  
 

文章来源: blog.csdn.net,作者:irrationality,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/weixin_54227557/article/details/120595285

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。