线段树/树状数组初等模版
使用线段树或树状数组维护区间和即可
线段树代码
#include<iostream>
using namespace std;
struct point{
int l,r;
long long sum;
int lc,rc;
};
point po[500001];
int a[500001];
int pcnt=0;//表示点个数,用于建树
int buildtree(int l,int r){
//申请点
int v=++pcnt;
po[v].l=l;
po[v].r=r;
if(l==r){
po[v].sum=a[l];
return v;
}
int mid=(l+r)/2;
po[v].lc= buildtree(l,mid);
po[v].rc= buildtree(mid+1,r);
po[v].sum=po[po[v].lc].sum+po[po[v].rc].sum;
return v;
}
void addval(int k,long long val,point &v){
v.sum+=val;
if(v.l==v.r) return;
int mid=(v.l+v.r)/2;
if(k<=mid) addval(k,val,po[v.lc]);
else addval(k,val,po[v.rc]);
}
long long getsum(int l,int r,point v){
if(l==v.l && r==v.r) return v.sum;
int mid=(v.l+v.r)/2;
if(r<=mid) return getsum(l,r,po[v.lc]);
else if(l>mid) return getsum(l,r,po[v.rc]);
else return getsum(l,mid,po[v.lc])+getsum(mid+1,r,po[v.rc]);
}
int main(){
//freopen("dynsum1.in","r",stdin);
int n,q,i;
int l,r,x;
cin>>n>>q;
for(i=1;i<=n;i++) cin>>a[i];
buildtree(1,n);
for(i=1;i<=q;i++){
cin>>x;
if(x==1){
cin>>l>>r;
r=r-a[l];
addval(l,(long long)r,po[1]);
a[l]+=r;
}else{
cin>>l>>r;
cout<<getsum(l,r,po[1])<<endl;
}
}
}
树状数组代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int lowbit(int x){
return x&(-x);
}
#define N 100001
long long arr[N];
long long init[N];
int n,m;
inline void updata(int k,long long val){
while(k<=n){
arr[k]+=val;
k+=lowbit(k);
}
}
inline long long getsum(int k){//求arr[1-k]的和
long long res=0;
while(k>0){
res+=arr[k];
k-=lowbit(k);
}
return res;
}
int main(){
int i,t,p,q;
memset(arr,0,sizeof(arr));
memset(init,0,sizeof(init));
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld",init+i);
updata(i,init[i]);
}
for(i=1;i<=m;i++){
scanf("%d %d %d",&t,&p,&q);
if(t==1){
updata(p,q-init[p]);
init[p]=q;
}else if(t==2) {
printf("%lld\n",getsum(q)-getsum(p-1));
}
}
}