問題描述
已知一個數(shù)列，你需要進行下面兩種操作：
1.將某一個數(shù)加上x
2.求出某區(qū)間每一個數(shù)的和
輸入文件
第一行包含兩個整數(shù)N瓤荔、M输硝，分別表示該數(shù)列數(shù)字的個數(shù)和操作的總個數(shù)程梦。
第二行包含N個用空格分隔的整數(shù)橘荠，其中第i個數(shù)字表示數(shù)列第i項的初始值哥童。
接下來M行每行包含3個整數(shù)褒翰，表示一個操作，具體如下：
操作1： 格式：1 x k 含義：將第x個數(shù)加上k
操作2： 格式：2 x y 含義：輸出區(qū)間[x,y]內(nèi)每個數(shù)的和
輸出文件
輸出包含若干行整數(shù)错邦，即為所有操作2的結果型宙。
樣例輸入
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
樣例輸出
14
16
#include<cstdio>
using namespace std;
int n,m,ans[500001];
int lowbit(int x){
return x & (-x);
}
void add(int x,int k){
for (;x<=n;x+=lowbit(x))
ans[x]+=k;
}
int sum(int x){
int sum=0;
for (;x>0;x-=lowbit(x))
sum+=ans[x];
return sum;
}
int main(){
int i,x,y,k,type;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++){
scanf("%d",&k);
add(i,k);
}
for (i=1;i<=m;i++){
scanf("%d",&type);
if (type==1){
scanf("%d%d",&x,&k);
add(x,k);
}
if (type==2){
scanf("%d%d",&x,&y);
printf("%d\n",sum(y)-sum(x-1));
}
}
return 0;
}
