算法思路
1.首先,通过一次遍历整数序列,计算得到前缀和数组 s[]。数组的每个元素 s[i] 表示的是原整数序列中前 i 个数的和。
2.然后,对于每个询问 [l, r],直接利用前缀和数组求解。区间 [l, r] 的和可以表示为 s[r] - s[l-1],其中 s[r] 表示整数序列中前 r 个数的和,s[l-1] 表示整数序列中前 l-1 个数的和。因此,通过这种方式可以在常数时间内得到区间 [l, r] 的和。
3.最终,输出每个询问的结果。
C++ 代码(详细注释)
#include<iostream>
using namespace std;
const int N=100000+10;
int n,m; // n,m分别表示整数序列的长度和询问次数
int a[N],s[N]; // 数组a和s用于存储整数序列和前缀和
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]); // 循环读入整数序列中的每个数到数组a中
// 计算整数序列的前缀和
for(int i=1;i<=n;i++)
s[i]=s[i-1]+a[i]; //s[i] 表示前缀和数组中第 i 个元素,即前 i 个数的和,a[i] 表示整数序列中第 i 个元素的值
// 循环处理每个询问
while(m--)
{
int l,r; // l和r表示当前询问的左右区间范围
scanf("%d%d",&l,&r);
printf("%d\n",s[r]-s[l-1]); //计算区间 [l, r] 内的整数序列和。数组的索引从 0 开始,因此l要减一,表示从第 1 个数到第 l-1 个数的和
}
return 0;
}