Responsive image

问题 F: 求区间和

问题 F: 求区间和

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 61
[提交][状态][讨论版][命题人:]

题目描述

给定n个正整数组成的数列a1,a2,⋯,an和m个询问，对于每次询问，请你求这个数列a中区间[li,ri]的区间和。
你想大暴力？再好好想想怎么优化一下吧。

输入描述

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

第二行，为n个正整数a1,a2,...,an。

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

接下来m行，每行为两个正整数li，ri满足1≤li≤ri≤n

输出描述

共m行。

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

样例输入

4
4 3 2 1
2
1 4
2 3

样例输出

10
5

提示


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



对于50%的数据：n，m≤1000；



对于100%的数据：1≤n，m≤100000，1≤ai≤100000。

[提交][状态]
ACM算法攻关部