计算区间和
题目描述
输入 n 个整数,再输入m个区间,每个区间的起点下标L,终点下标R。
对于每个区间,输出n个整数中从下标 L 到下标 R 的区间和。
输入格式
第一行包括两个整数n和m。(1≤n,m≤500000)
第二行包括n个整数a。(1≤ai≤100)
接下来有m行,每行包含两个整数L和R,表示区间范围。(0<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
- 第 2 个查询 L=1,R=9:a1+a2+...+a9=2+1+3+6+4+20+15+10+4=65
- 第 3 个查询 L=5,R=8:a5+a6+a7+a8=4+20+15+10=49
数据规模与约定
对于 100% 的数据,
1≤n,m≤500000
1≤ai≤100
1≤L≤R≤n
提示
- 如果对每个查询都使用循环累加,单次查询最坏为 O(n),总复杂度为 O(nm),当 n,m达到 5×105 时会超时。
- 使用前缀和可以将每次查询降到 O(1),总复杂度为 O(n+m)。
- 前缀和公式:si=si−1+ai,则区间 [L,R] 的和为sR−sL−1 。
- 注意使用 long long 存储前缀和,防止溢出(本题 ai≤100,n≤5×105,最大前缀和为 5×107,int 也可存下,但养成使用 long long 的习惯更安全)。
- 由于输入量较大,建议使用 scanf/printf 或关闭同步流的 cin/cout 以加快输入输出速度。