记录编号	12452	评测结果	AAAAAAAAAA
题目名称	求和问题	最终得分	100
用户昵称	yanzheng	是否通过	通过
代码语言	C	运行时间	0.559 s
提交时间	2009-09-12 12:37:19	内存使用	1.00 MiB

#include <stdio.h>

long long n;
long long in[100001];

long long lowbit(long long x);
void plus(long long pos,long long num);
long long sum(long long end);

int main()
{
    FILE *in,*out;
    in=fopen("sum.in","r");
    out=fopen("sum.out","w");
    long long i,j,k,m,ans;
    int t;

    fscanf(in,"%lld",&n);
    for(k=1;k<=n;k++)
    {
        fscanf(in,"%lld",&i);
        plus(k,i);
    }

    fscanf(in,"%lld",&m);

    for(t=0;t<(int)m;t++)
    {
        fscanf(in,"%lld%lld",&i,&j);
        ans=sum(j)-sum(i-1);
        fprintf(out,"%lld\n",ans);
        if(k==1) exit(0);
    }

    return 0;
}

long long lowbit(long long x)
{
    return x&(x^(x-1));
}

void plus(long long pos,long long num)
{
    while(pos <= n)
    {
          in[pos]+=num;
          pos+=lowbit(pos);
    } 
}

long long sum(long long end)
{
    long long sum=0;
    while(end>0)
    { 
          sum+=in[end];
          end-=lowbit(end);
    }
    return sum;
}