B3612 【深进1.例1】求区间和洛谷题解

题解"/>

B3612 【深进1.例1】求区间和洛谷题解

文章目录

• 题目
• • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
  • 提示
• 代码

题目

题目描述

给定 n n n 个正整数组成的数列 a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_n a1​,a2​,⋯,an​ 和 m m m 个区间 [ l i , r i ] [l_i,r_i] [li​,ri​]，分别求这 m m m 个区间的区间和。

输入格式

第一行，为一个正整数 n n n 。

第二行，为 n n n 个正整数 a 1 , a 2 , ⋯ , a n a_1,a_2, \cdots ,a_n a1​,a2​,⋯,an​

第三行，为一个正整数 m m m 。

接下来 m m m 行，每行为两个正整数 l i , r i l_i,r_i li​,ri​ ，满足 1 ≤ l i ≤ r i ≤ n 1\le l_i\le r_i\le n 1≤li​≤ri​≤n

输出格式

共 m m m 行。

第 i i i 行为第 i i i 组答案的询问。

样例 #1

样例输入 #1

4
4 3 2 1
2
1 4
2 3

样例输出 #1

10
5

提示

样例解释：第 1 到第 4 个数加起来和为 10。第 2 个数到第 3 个数加起来和为 5。

对于 50% 的数据： n , m ≤ 1000 n,m\le 1000 n,m≤1000 ；

对于 100% 的数据： 1 ≤ n , m ≤ 1 0 5 1 \leq n,m\le 10^5 1≤n,m≤105， 1 ≤ a i ≤ 1 0 4 1 \leq a_i\le 10^4 1≤ai​≤104。

代码

// 使用前缀和
#include <iostream>
using namespace std;
int a[100005],n,q,l,r,sa[100005];
int main()
{cin>>n;for(int i=1; i<=n; i++){cin>>a[i];sa[i]=a[i]+sa[i-1];}cin>>q;for(int i=1; i<=q; i++){cin>>l>>r;cout<<sa[r]-sa[l-1]<<endl;}return 0;
}