记录编号	161674	评测结果	AAAAAAAAAA
题目名称	求和问题	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.476 s
提交时间	2015-05-08 06:47:37	内存使用	4.10 MiB

#include <cstdio>
#include <cstring>
 
using namespace std;
 
void work();
void modify(int,int);
int lowbit(int);
long long sum(int);
 
long long data[500001],temp;
int n,l,r;
 
int main()
{
    work();
    return 0;
}
 
void work()
{
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&temp);
        modify(i,temp);
    }
    scanf("%lld",&temp);
	for(int i=1;i<=temp;i++)
	{
        scanf("%d%d",&l,&r);
        printf("%lld\n",sum(r)-sum(l-1));
    }
    return;
}
 
int lowbit(int x)
{
    return x&(-x);
}
 
void modify(int pos,int ds)
{
    while(pos<=n)
    {
        data[pos]+=ds;
        pos+=lowbit(pos);
    }
    return;
}
 
long long sum(int i)
{
    long long sk=0;
    while(i>0)
    {
        sk+=data[i];
        i-=lowbit(i);
    }
    return sk;
}