记录编号	225387	评测结果	AAAAAAAAAA
题目名称	求和问题	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.796 s
提交时间	2016-02-17 10:52:47	内存使用	0.92 MiB

#include<iostream>
#include<fstream>
#include<sstream>
#include<iomanip>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=10010;
struct tree{
	int l,r;
	long long sum;
	tree(){
		l=r=0;
		sum=0;
	}
}node[maxn<<2];
void build(int,int,int);
long long qery(int,int,int);
int n,m;
int main(){
#define COGS
#ifdef COGS
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
#endif
	scanf("%d",&n);
	build(1,n,1);
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%llu\n",qery(a,b,1));
	}
#ifdef COGS
	fclose(stdin);fclose(stdout);
#endif
	return 0;
}
void build(int l,int r,int rt){
	node[rt].l=l;node[rt].r=r;
	if(l==r){
		scanf("%llu",&node[rt].sum);
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	node[rt].sum=node[rt<<1].sum+node[rt<<1|1].sum;
}
long long qery(int a,int b,int rt){
	int l=node[rt].l,r=node[rt].r;
	if(a<=l&&b>=r)return node[rt].sum;
	int mid=(l+r)>>1;
	if(b<=mid)return qery(a,b,rt<<1);
	if(a>mid)return qery(a,b,rt<<1|1);
	return qery(a,b,rt<<1)+qery(a,b,rt<<1|1);
}