记录编号	228313	评测结果	AAAAAAAAAA
题目名称	求和问题	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.733 s
提交时间	2016-02-19 09:58:56	内存使用	0.40 MiB

//树状数组 

#include<cstdio>
using namespace std;

typedef long long LL;
LL A[10100]={0},C[10010]={0};
int n=0;

LL ReadL()
{
	char ch=getchar();
	LL x=0;
	while(ch<'0'||ch>'9')	ch=getchar();
	while(ch<='9'&&ch>='0'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

int ReadI()
{
	char ch=getchar();
	int x=0;
	while(ch<'0'||ch>'9')	ch=getchar();
	while(ch<='9'&&ch>='0'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

inline int Lowbit(int x)
{
	return x&-x;//***********************
}

inline LL GetSum(int x){
	LL tot=0;
	for(int i=x;i>0;i-=Lowbit(i)){
		tot+=C[i];
	}
	return tot;
}

inline void Update(int x, LL y)
{
	for(int i=x; i<=n;i+=Lowbit(i)){
		C[i]+=y;
	}
}

void Init()
{
	n=ReadI();
	for(int i=1;i<=n;i++){
		A[i]=ReadL();
		Update(i,A[i]);
	}
	int m;//询问 
	m=ReadI();
	for(int i=1;i<=m;i++){
		int x, y;
		x=ReadI();
		y=ReadI();
		LL ans=GetSum(y)-GetSum(x-1);
		printf("%lld\n",ans);
	}
}

int main()
{
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	Init();
	return 0;
}