记录编号	228295	评测结果	AAAAAAAAAA
题目名称	求和问题	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.077 s
提交时间	2016-02-19 09:45:56	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int maxn=10010;
LL c[maxn]={0},n,m;
void update(int,LL);
LL sum(int,int);
LL sum(int);
LL min(int);
LL max(int);
int lowbit(int);
int main(){
#define COGS
#ifdef COGS
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		LL num;
		scanf("%lld",&num);
		update(i,num);
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		int s,t;
		scanf("%d%d",&s,&t);
		printf("%lld\n",sum(s,t));
	}
	
	return 0;
}
void update(int x,LL num){
	while(x<=n){
		c[x]+=num;
		x+=x&-x;
	}
}
LL sum(int s,int t){
	if(s!=1)return sum(1,t)-sum(1,s-1);
	LL result=0;
	for(int i=t;i;i-=lowbit(i))result+=c[i];
	return result;
}
LL sum(int t){
	return sum(1,t);
}
LL min(int t){
	LL result=0x7fffffffffffffff;
	for(int i=t;i;i-=lowbit(t))if(c[i]<result)result=c[i];
	return result;
}
LL max(int t){
	LL result=-0x7ffffffffffffff;
	for(int i=t;i;i-=lowbit(t))if(c[i]>result)result=c[i];
	return result;
}
inline int lowbit(int x){
	return x&-x;
}