记录编号	136430	评测结果	AAAAAAAAAA
题目名称	36.求和问题	最终得分	100
用户昵称	高哥	是否通过	通过
代码语言	C++	运行时间	0.485 s
提交时间	2014-11-02 21:50:11	内存使用	0.35 MiB

//树状数组球区间和
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 10010
#define ll long long 
#define lowbit(x) (x&-x)
using namespace std;
ll c[N],n;
void up(int x,ll d)
{
	while(x<=n)
	{
		c[x]+=d;
		x+=lowbit(x);
	}
}
ll getsum(int x)
{
	ll ans=0;
	while(x>0)
	{
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}
int main()
{
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		int d;
		scanf("%lld",&d);
		up(i,d);
	}
	int m;
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%lld\n",getsum(r)-getsum(l-1));
	}
	return 0;
}