一维前缀和
针对问题
输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。
对数据的要求
n，l，r大小约为1e6，即能开数组存放序列a[n]
代码实现
const int N = 1e6 +10;
int sum[N], a[N];
for(int i=0; i<N; i++){
scanf("%d", &a[i]);
}
sum[0] = a[0];
for(int i=1; i<N; i++){
sum[i] = sum[i-1] + a[i];
}
int n;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d%d", &l, &r);
printf("%d\n", sum[r]-sum[l-1]);
}
原理
sum[i]存放i之前的所有数据的和，即sum[i] = a[1] + a[2] + a[3] ... a[i]。
由此，从第l个数到第r个数的和 = sum[r]-sum[l-1]。
