#O1006. 区间和

区间和

区间和(前缀和)

题目描述

给定一个长度为 nn 的整数序列 a1,a2,…,ana_1, a_2, \ldots, a_n,共有 qq 次询问,每次询问给出 l,rl, r,求

∑i=lrai=al+al+1+⋯+ar\sum_{i=l}^{r} a_i = a_l + a_{l+1} + \cdots + a_r

输入格式

第一行一个整数 nn。

第二行 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n,相邻两数之间用一个空格隔开。

第三行一个整数 qq。

接下来 qq 行,每行两个整数 l,rl, r。

输出格式

共 qq 行,每行一个整数,表示对应询问的区间和。

样例 #1

样例输入 #1

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

样例输出 #1

15
2
6

数据规模与约定

数据范围 nn qq aia_i
全部测试点 1≤n≤1061 \le n \le 10^6 1≤q≤1051 \le q \le 10^5 −109≤ai≤109-10^9 \le a_i \le 10^9
  • 区间和最大可达 101510^{15},可能超出 32 位整数范围。
  • 保证 1≤l≤r≤n1 \le l \le r \le n。
  • 多次询问,逐次暴力累加区间元素会在最大数据下超时。