线段树
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n,m;
struct Node{
int l,r;
int sum;
}t[N*4];
void pushup(int p)
{
t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
}
void build(int p,int l,int r)
{
t[p].l = l,t[p].r = r;
if(l == r){
t[p].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(p << 1,l,mid);
build(p << 1 | 1,mid + 1,r);
pushup(p);
}
void change(int p,int x,int c)
{
if(t[p].l == t[p].r){
t[p].sum += c;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if(x <= mid) change(p << 1,x,c);
else change(p << 1 | 1,x,c);
pushup(p);
}
int query(int p,int l,int r)
{
if(l <= t[p].l && r >= t[p].r) return t[p].sum;
int res = 0;
int mid = (t[p].l + t[p].r) >> 1;
if(l <= mid) res += query(p << 1,l,r);
if(r > mid) res += query(p << 1 | 1,l,r);
return res;
}
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i++) scanf("%d",a + i);
build(1,1,n);
while(m--){
int k,a,b;
cin>>k>>a>>b;
if(k == 1) change(1,a,b);
else cout<<query(1,a,b)<<endl;
}
return 0;
}
树状数组
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n,m;
int a[N];
struct Node{
int l,r;
int sum;
}t[N * 4];
void backup(int p)
{
t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
}
void build(int p,int l,int r)
{
t[p].l = l,t[p].r = r;
if(l == r){
t[p].sum = a[l];
return;
}
int mid = l + r >> 1;
build(p << 1,l,mid);
build(p << 1 | 1,mid + 1,r);
backup(p);
}
void change(int p,int x,int c)
{
if(t[p].l == t[p].r){
t[p].sum += c;
return;
}
int mid = t[p].l + t[p].r >> 1;
if(x <= mid) change(p << 1,x,c);
else change(p << 1 | 1,x,c);
backup(p);
}
int query(int p,int l,int r)
{
if(l <= t[p].l && r >= t[p].r) return t[p].sum;
int res = 0;
int mid = t[p].l + t[p].r >> 1;
if(l <= mid) res += query(p << 1,l,r);
if(r > mid) res += query(p << 1 | 1,l,r);
return res;
}
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i++) scanf("%d",a + i);
build(1,1,n);
while(m--){
int k,a,b;
cin>>k>>a>>b;
if(k == 1) change(1,a,b);
else cout<<query(1,a,b)<<endl;
}
return 0;
}