#qc004. 计算区间和

计算区间和

计算区间和

题目描述

​ 输入 n 个整数,再输入m个区间,每个区间的起点下标L,终点下标R。

​ 对于每个区间,输出n个整数中从下标 L 到下标 R 的区间和。

输入格式

​ 第一行包括两个整数n和m。(1≤n,m≤5000001≤n,m≤500000) ​ 第二行包括n个整数a。(1≤ai≤1001≤a_i≤100) ​ 接下来有m行,每行包含两个整数L和R,表示区间范围。(0<L≤R≤n0<L≤R≤n)

输出格式

​ 输出有m行,每行一个整数,表示一个区间和。

输入输出样例

10 3
2 1 3 6 4 20 15 10 4 11
3 7
1 9
5 8
48
65
49

样例解释

原数组为:$a_1=2, a_2=1, a_3=3, a_4=6, a_5=4, a_6=20, a_7=15, a_8=10, a_9=4, a_{10}=11。$

  • 第 1 个查询L=3,R=7:a3+a4+a5+a6+a7=3+6+4+20+15=48 L=3,R=7:a_3+a_4+a_5+a_6+a_7=3+6+4+20+15=48
  • 第 2 个查询 L=1,R=9:a1+a2+...+a9=2+1+3+6+4+20+15+10+4=65L=1,R=9:a_1+a_2+...+a_9=2+1+3+6+4+20+15+10+4=65
  • 第 3 个查询 L=5,R=8:a5+a6+a7+a8=4+20+15+10=49L=5,R=8:a_5+a_6+a_7+a_8=4+20+15+10=49

数据规模与约定

​ 对于 100% 的数据,

​ 1≤n,m≤5000001≤n,m≤500000

​ 1≤ai≤1001≤a_i≤100

​ 1≤L≤R≤n1≤L≤R≤n

提示

  • 如果对每个查询都使用循环累加,单次查询最坏为 O(n)O(n),总复杂度为 O(nm)O(nm),当 n,m达到 5×1055×10^5 时会超时。
  • 使用前缀和可以将每次查询降到 O(1),总复杂度为 O(n+m)O(n+m)。
  • 前缀和公式:si=si−1+ais_i=s_{i−1}+a_i,则区间 [L,R] [L,R] 的和为sR−sL−1s_R−s_{L−1} 。
  • 注意使用 long long 存储前缀和,防止溢出(本题 ai≤100,n≤5×105a_i≤100,n≤5×10^5,最大前缀和为 5×1075×10^7,int 也可存下,但养成使用 long long 的习惯更安全)。
  • 由于输入量较大,建议使用 scanf/printf 或关闭同步流的 cin/cout 以加快输入输出速度。