例题
洛谷P3374【模板】树状数组1
主要思路
参考大佬的博客
代码
#include
#include
using namespace std;
int d[500001];
int n, m, x, y, k, com;
int lowbit(int x){ // 树状数组主要函数
return x & (-x);
}
int src(int x){ // 1~x区间和查询
int ans = 0;
while(x){
ans += d[x];
x -= lowbit(x);
}
return ans;
}
void add(int x, int v){ // x位置数据更新,d[x]+v
while(x <= n){
d[x] += v;
x += lowbit(x);
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
int in;
cin >> in;
add(i, in); // 初始化
}
for(int i = 0; i < m; i++){
scanf("%d", &com);
if(com == 1){
scanf("%d %d", &x, &k);
add(x, k);
}
else if(com == 2){
scanf("%d %d", &x, &y);
printf("%d\n", src(y) - src(x-1));
}
}
}
Comments | NOTHING