记录编号	228840	评测结果	AAAAAAAAAA
题目名称	求和问题	最终得分	100
用户昵称	水墨青花	是否通过	通过
代码语言	C++	运行时间	0.977 s
提交时间	2016-02-19 19:25:16	内存使用	3.03 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

long long a[200001],c[200001];
int n,m;

long long Getsum(int x);
int Lowbit(int x);
void Update(int x,long long y);

int main()
{
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int a;
		scanf("%d",&a);
		Update(i,a);
	}
	
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int s,e;
		scanf("%d%d",&s,&e);
		printf("%lld\n",Getsum(e)-Getsum(s-1));
	}
	
	
	fclose(stdin);
	fclose(stdout);	
	return 0;
}


int Lowbit(int x)
{
	return x&(-x);
}

long long Getsum(int x)
{
	long long total=0; 
	for(int i=x;i>0;i-=Lowbit(i))
	{
		total+=c[i];
	}
	return total;
}

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