LG#P8218. 求区间和

求区间和

P8218 【深进1.例1】求区间和

题目描述

\hspace{15pt}给定由 nn 个正整数组成的序列 a1,a2,…,ana_1,a_2,\dots,a_n 和 mm 个区间 [li,ri][l_i,r_i],分别求这 mm 个区间的区间和。

输入格式

\hspace{15pt}第一行输入一个正整数 n(1≦n≦105)n \left(1 \leqq n \leqq 10^5\right) 代表序列的长度。

\hspace{15pt}第二行输入 nn 个正整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^4\right)$ 代表序列中的元素。

\hspace{15pt}第三行输入一个正整数 m(1≦m≦105)m \left(1 \leqq m \leqq 10^5\right) 代表区间的数量。

\hspace{15pt}此后 mm 行,第 ii 行输入两个正整数 li,ri(1≦li≦ri≦n)l_i,r_i \left(1 \leqq l_i \leqq r_i \leqq n\right) 代表第 ii 个区间。

输出格式

\hspace{15pt}输出 mm 行,第 ii 行输出一个整数,代表第 ii 个区间的区间和。

测试样例

4
4 3 2 1
2
1 4
2 3
10
5

样例 1 解释

\hspace{15pt}第 11 个区间为 [1,4][1,4],第 11 到第 44 个数加起来和为 4+3+2+1=104+3+2+1=10;第 22 个区间为 [2,3][2,3],第 22 个数到第 33 个数加起来和为 3+2=53+2=5。

数据范围与提示

\hspace{15pt}对于 50%50\% 的数据,n,m≦1000n,m \leqq 1000。