3198: 区间和 

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte

Total Submit: 643            Accepted:202

Description

给定n个数据，有两个操作，加减其中的一个数据，当然还可查询在某段数据的和。

Input

 

输入数据有多组，每组数据的

第一行输入n，1=<n<=500000,代表数据的个数。

第二行输入具体数据，数据为正整数，范围在1到10000.

第三行输入m，1<=m<=100000,表示操作的次数。包含了修改和查询操作。

下面m行就是具体的操作了。

C i x  表示为第i个元素加上x，x范围在1到10000.

Q i j  表示查询区段i到j的和。保证输入的i<=j.

以EOF结束。

 

Output

输出查询后的区段和。

Sample Input

8

1 5 9 11 2 8 15 6

4

Q 1 3

C 2 10

Q 1 4

Q 2 5

Sample Output

15

36

37

单点更新，单点查询

区间查询就是查询把值放在段里面

#include 
       
        typedef __int64 ll;const int N =500005;ll c[N];int n;int lowbit(int x){    return x&-x;}void add(int x,int d){    while(x<=n)    {        c[x]+=d;        x+=lowbit(x);    }}ll sum(int x){    ll ans=0;    while(x>0)    {        ans+=c[x];        x-=lowbit(x);    }    return ans;}int main(){    while(~scanf("%d",&n))    {        for(int i=1;i<=n;i++)            c[i]=0;        for(int i=1;i<=n;i++)        {            int x;            scanf("%d",&x);            add(i,x);        }        int m;        scanf("%d",&m);        while(m--)        {            getchar();            char c;            int a,b;            scanf("%c%d%d",&c,&a,&b);            if(c=='Q')printf("%I64d\n",sum(b)-sum(a-1));            else add(a,b);        }    }    return 0;}
       

想学习更多技巧可以到的