记录编号	228202	评测结果	AAAAAAAEWW
题目名称	求和问题	最终得分	70
用户昵称	SOBER GOOD BOY	是否通过	未通过
代码语言	C++	运行时间	2.026 s
提交时间	2016-02-19 09:14:53	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long 
using namespace std;
const int maxn=10100;
int m,n,len=0,c[maxn]={0};
void Init();
void  jianshu();
void  updata(int , LL );
LL getsum(LL int x);
int main(){
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	Init();
	jianshu();
	int h;
	cin>>h;
	for(int i=1;i<=h;i++)
	{
		LL int x,y;
		scanf("%lld%lld",&x,&y);	LL k=getsum(y)-getsum(x-1);
		printf("%d",k);
	}
	return 0;
}
void Init()
{
	scanf("%d",&n);
}
void jianshu()
{
	for(int i=1;i<=n;i++)
	{
		LL int y;
		scanf("%lld",&y);
		updata(i,y);
	}
}
LL lowbit(LL int x)
{
	LL k=x&(-x);
	return k;
}
LL getsum(LL int x){
	LL tot=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		tot+=c[i];
	}
	return tot;	
}
void updata(int x, LL int y)
{
	while(x<=n)
	{
		c[x]+=y;int k=x&(-x);
		x+=k;
	}
}