求助区间和的莫队做法虽然可以用前缀和

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
struct Q{
	int l,r,k;
}val[maxn];
int a[maxn];
int pos[maxn];
int ans[maxn];
int res;
void add(int x){
	res+=a[x];
}
void sub(int x){
	res-=a[x];
}
int main() {
	int n,m;cin>>n>>m;
	int size=sqrt(n);//块的大小
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pos[i]=i/size;
	}
	for(int i=1;i<=m;i++){
		cin>>val[i].l>>val[i].r;
		val[i].k=i;
	}
	sort(val+1,val+1+m,[](Q x,Q y){
		return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];
	});
	int ln=1,rn=0;//初始化
	for(int i=1;i<=m;i++){
		while(val[i].l<ln)add(--ln);
		while(val[i].r>rn)add(++rn);
		while(val[i].l>ln)sub(++ln);
		while(val[i].r<rn)sub(--rn);
		ans[val[i].k]=res;
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}