最基础树状数组
title: 最基础树状数组
categories:
- ICPC
tags:
- null
abbrlink: 7d5ff616
date: 2023-05-28 00:00:00
1.单点加
2.前缀和查询
int n, m;
int a[N];
int tr[N];
int lowbit(int x){
return x&(-x);
}
void add(int pos,int k){
for(int i=pos;i<=n;i+=lowbit(i))tr[i]+=k;
}
int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))res+=tr[i];
return res;
}
void solve(){
cin>>n;cin>>m;
for(int i=1;i<=n;i++){
int x;cin>>x;
add(i,x);
}
while(m--){
int op;cin>>op;
if(op==1){
int pos,val;cin>>pos>>val;
add(pos,val);
}
else {
int l,r;cin>>l>>r;
cout<<query(r)-query(l-1)<<endl;
}
}
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!