记录编号	304184	评测结果	AAAAAAAATA
题目名称	求和问题	最终得分	90
用户昵称	仰望星空	是否通过	未通过
代码语言	C++	运行时间	6.284 s
提交时间	2016-09-07 20:01:00	内存使用	19.17 MiB

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll a[100001];
 
struct tree
{
	ll l,r,sum;
	
}t[1000001];
 
void build(ll l,ll r,ll k)
{
	t[k].l=l;
	t[k].r=r;
	if(l==r)
	{
		t[k].sum=a[l];
		return;
	}
	ll mid=(l+r)/2;
	build(l,mid,k*2);
	build(mid+1,r,k*2+1);
	t[k].sum=t[k*2].sum+t[k*2+1].sum;
	return;
}
 
ll query(ll l,ll r,ll k)
{
	if(t[k].l==l&&t[k].r==r)return t[k].sum;
	int mid=(t[k].l+t[k].r)/2;
	if(r<=mid)return query(l,r,k*2);
	if(l>mid)return query(l,r,k*2+1);
	return query(l,mid,k*2)+query(mid+1,r,k*2+1);
}
 
int main()
{
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	ll n,m,i,j,k;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,n,1);
	cin>>m;
	for(i=1;i<=m;i++)
	{
		cin>>j>>k;
		cout<<query(j,k,1)<<endl;
	}
	return 0;
}