前缀和模板题

题目描述

给出一个数字$n$表示有个数字，

给出$n$个整数$a_1$,$a_2$,...$a_n$;

给出一个数字$m$ 有$m$个询问： 每次询问给出两个整数$s$,$e$，请求出 $a_s + a_{s+1}...a_e$

输入格式

第一行一个整数$n$

第二行$n$个整数$a_1$,$a_2$,...$a_n$;

第三行一个整数$m$,保证m是不大于100000的正整数

随后m行每行两个整数 s，e，($e >= s$)

输出格式

m个整数，每一个换一行

样例 #1

样例输入 #1

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

样例输出 #1

3
5
15

提示

$n <= 10^5$,$a_i <= 10^4$。

同学们请注意计算这道题的时间复杂度