正经题解｜学情调查

统计$M$个数中指定区间范围的总和，最简单的方式就是一个一个累加，每次查询的时间复杂度为 $O(N)$。但查询次数$M$较大时，复杂度会达到 $O(N*M)$ ，会出现超时。考虑到每次查询都是查询区间和，不同区间和的计算有相同的部分，所以可以采用前缀和的方式来进行区间求和。这样用一次减法代替循环求和，能大大减少查询所消耗的时间。

#include <bits/stdc++.h>
using namespace std;
long long a[1000010];
long long s[1000010];
int main () {
	long long n,m;
	long long i;
	scanf("%lld%lld",&n,&m);
	a[0]=0;
	s[0]=0;
	for(i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		s[i]=s[i-1]+a[i];
	}
	long long l,r;
	double sum;
	double ave;
	for(i=1;i<=m;i++){
		scanf("%lld%lld",&l,&r);
		sum=s[r]-s[l-1];//注意转化为浮点数再计算平均值
		ave=sum/(r-l+1);
		printf("%.2f\n",ave);
	}
	return 0;
}