线段树做法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, m;
int w[N];
struct Node{
int l, r;
int sum;
}tr[N * 4];
void pushup(int k){
tr[k].sum = tr[k << 1].sum + tr[k << 1 | 1].sum;
}
void build(int k, int l, int r){
if(l == r){
tr[k] = {l, r, w[r]};//不用往下找
return;
}
tr[k] = {l, r};
int mid = l + r >> 1;
build(k << 1, l, mid);//左子树
build(k << 1 | 1, mid + 1, r);//右子树
pushup(k);
}
void modify(int k, int lr, int x){
if(tr[k].l == tr[k].r){
tr[k].sum += x;
return;
}
int mid = tr[k].l + tr[k].r >> 1;
if(lr > mid) modify(k << 1 | 1, lr, x);
else modify(k << 1, lr, x);
pushup(k);
}
int query(int k, int l, int r){
if(tr[k].l >= l && tr[k].r <= r) return tr[k].sum;
int mid = tr[k].l + tr[k].r >> 1;
int sum = 0;
if(l <= mid) sum += query(k << 1, l, r);
if(r > mid) sum += query(k << 1 | 1, l, r);
return sum;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> w[i];
build(1, 1, n);
while(m -- ){
int k, a, b;
cin >> k >> a >> b;
if(k == 0) cout << query(1, a, b) << endl;
else modify(1, a, b);
}
return 0;
}
树状数组做法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int a[N], tr[N];
int n, m;
inline int lowbit(int x){
return x & -x;
}
int query(int k){
int res = 0;
for(int i = k; i ; i -= lowbit(i)) res += tr[i];
return res;
}
void add(int k, int x){
for(int i = k; i <= n; i += lowbit(i)) tr[i] += x;
}
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]);
while(m -- ){
int k, x, y;
cin >> k >> x >> y;
if(k == 0) cout << query(y) - query(x - 1) << endl;
else add(x, y);
}
return 0;
}