题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

输入格式

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3个整数，表示一个操作，具体如下：

操作1： 格式：1 x k 含义：将第x个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

输入 #1复制

5 51 5 4 2 31 1 32 2 51 3 -11 4 22 1 4

输出 #1复制

1416

说明/提示

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

样例说明：

故输出结果14、16

单点 修改，区间查询

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=500005; int n,m;int a[N]; int lowbit(int l){return l&(-l);} void update(int l,int u){//读入操作    for(;l<=n;l+=lowbit(l)){        a[l]+=u;    }} int sum(int k){//前缀求和    int an=0;    for(;k;k-=lowbit(k)){        an+=a[k];    }    return an;} int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++){        int u;        scanf("%d",&u);        update(i,u);    }    //for(int i=1;i<=n;i++){    //  printf("%d ",a[i]);    //}    //printf("\n");    for(int i=1;i<=m;i++){        int p,k,l;        scanf("%d%d%d",&p,&k,&l);        if(p==1){            for(int j=k;j<=n;j+=lowbit(j)){                a[j]+=l;            }        }        else{            printf("%d\n",sum(l)-sum(k-1));//将l-r的区间理解为r的前缀和减去（l-1）的前缀和        }    }    return 0;}