模板题,没什么好说的。但是,数组要开4N!!!别像我一样RE三次
#include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> #define M 500050 using namespace std; int n,m,ans,cnt; int a[M<<2]; struct tree{ int l,r,da; }tr[M<<2]; void Build(int l,int r,int x){//建树 cnt++; tr[x].l=l; tr[x].r=r; if(l==r) return ; int mid=(l+r)>>1; Build(l,mid,x<<1); Build(mid+1,r,x<<1|1); } inline int Add(int x){//加点 if(tr[x].l==tr[x].r){ tr[x].da=a[tr[x].r]; return tr[x].da; } tr[x].da=Add(x<<1)+Add(x<<1|1); return tr[x].da; } void Plus(int x,int dis,int k){//区间修改 tr[x].da+=k; if(tr[x].l==tr[x].r) return ; if(dis<=tr[x<<1].r) Plus(x<<1,dis,k); if(dis>=tr[x<<1|1].l) Plus(x<<1|1,dis,k); } void Search(int x,int l,int r){//区间查找 if(tr[x].l>=l && tr[x].r<=r){ ans+=tr[x].da; return ; } if(tr[x<<1].r>=l) Search(x<<1,l,r); if(tr[x<<1|1].l<=r) Search(x<<1|1,l,r); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); Build(1,n,1); Add(1); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); if(x==1) Plus(1,y,z); else{ ans=0; Search(1,y,z); printf("%d\n",ans); } } return 0; }