参考链接:树状数组
树状数组解法
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010, M = 100010;
int n,m;
int a[N],tree[N];
int lowbit(int x){
return x & -x;
}
void add(int index, int num){
while(index <= n){
tree[index] += num;
index += lowbit(index);
}
}
int query(int index){
int res = 0;
while(index > 0){
res += tree[index];
index -= lowbit(index);
}
return res;
}
int main(){
cin>>n>>m;
for(int i = 1; i <= n; i++) cin>>a[i];
for(int i = 1; i <= n; i++) add(i, a[i]);
int k,a,b;
while(m--){
cin>>k>>a>>b;
if(!k) printf("%d\n", query(b) - query(a-1));
else add(a,b);
}
return 0;
}