我打了线段树和树状数组后才发现可以用前缀和，甚至暴力也可以过！QWQ

看一下我代码：

线段树

#include <bits/stdc++.h>
using namespace std;
struct tree
{
	int l,r;
	int sum;
}tr[414514];
int a[114514];
void push_up(int x)
{
    tr[x].sum=tr[x<<1].sum+tr[(x<<1)|1].sum;
}
void build(int l,int r,int x)
{
	if(l==r)
	{
		tr[x].sum=a[r];
		tr[x].l=l;
		tr[x].r=r;
	}
	else
	{
		tr[x].l=l;
		tr[x].r=r;
		int mid=l+r>>1;
		build(l,mid,x<<1);
		build(mid+1,r,x<<1|1);
		push_up(x);
	}
}
int query(int l,int r,int x)
{
	if(tr[x].l>=l&&tr[x].r<=r)
	{
		return tr[x].sum;
	}
	int sum=0;
	int mid=tr[x].l+tr[x].r>>1;
	if(l<=mid) sum=query(l,r,x<<1)+sum;
	if(r>=mid+1) sum=query(l,r,x<<1|1)+sum;
	return sum;
}
void modify(int x,int g,int v)
{
	if(tr[x].l==tr[x].r) tr[x].sum=v;
	else
	{
		int mid=tr[x].l+tr[x].r>>1;
		if(g<=mid) modify(x<<1,g,v);
		else if(g>mid) modify(x<<1|1,g,v);
		push_up(x);
	}
}
int main()
{
	int n,m;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	build(1,n,1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int time;
		time=query(x,y,1);
		printf("%d\n",time);
	}
	return 0;
}

树状数组

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[1000001],tr[1000001];
void push(int x,int v)
{
	while(x<=n)
	{
		tr[x]+=v;
		x+=x&(-x);
	}
}
int query(int x)
{
	int sum=0;
	while(x>0)
	{
		sum+=tr[x];
		x-=x&(-x);
	}
	return sum;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		push(i,a[i]);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d %d",&l,&r);
		printf("%d\n",query(r)-query(l-1));
	}
	return 0;
}