今天终于看懂树状函数了 看懂之后果然感觉比线段树简单便捷地多
就拿这题简单的单点更新来练手了
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; int a[50000+10]; int c[50000+10]; int lowbit(int x) { return x&(-x); } int sum(int x) { int ret=0; while(x>0) { ret+=c[x];x-=lowbit(x); } return ret; } void add(int x,int d) { while(x<=n) { c[x]+=d;x+=lowbit(x); } } int main() { int t,coun=1; int i,j; char s[30]; cin>>t; while(t--) { memset(c,0,sizeof(c)); printf("Case %d: ",coun++); cin>>n; for(i=1;i<=n;i++) { scanf("%d",&a[i]); add(i,a[i]); } while(scanf("%s",s)) { if(s[0]=='E') break; else if(s[0]=='A'||s[0]=='S') { int x,d; scanf("%d%d",&x,&d); if(s[0]=='S') d*=-1; add(x,d); } else if(s[0]=='Q') { int l,r,ans; scanf("%d%d",&l,&r); ans=sum(r)-sum(l-1); printf("%d ",ans); } } } return 0; }
线段树
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int sum[200000+100]; int n; void push(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) { if(l==r){scanf("%d",&sum[rt]); return ;} int m=(l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); push(rt); } void update(int key,int add,int l,int r,int rt) { if(l==r) {sum[rt]+=add;return ;} int m=(l+r)>>1; if(key<=m) { update(key,add,l,m,rt<<1); } else update(key,add,m+1,r,rt<<1|1); push(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) {return sum[rt];} int ret=0; int m=l+(r-l)/2; if(L<=m) { ret+=query(L,R,l,m,rt<<1); } if(m<R) { ret+=query(L,R,m+1,r,rt<<1|1); } return ret; } int main() { int t,coun=1; int i,j,k; int l,r,num,add; char que[20]; scanf("%d",&t); while(t--) { scanf("%d",&n); build(1,n,1); printf("Case %d: ",coun++); while(scanf("%s",que)) { if(que[0]=='E') break; else if(que[0]=='Q') { scanf("%d%d",&l,&r); printf("%d ",query(l,r,1,n,1)); } else { scanf("%d%d",&num,&add); if(que[0]=='S') add=-add; update(num,add,1,n,1); } } } return 0; }