数列的单点修改、区间求和
树状数组或线段树入门题
1 #include2 #include 3 4 int c[50005],N; 5 6 void add(int x,int a){ 7 while(x<=N){ 8 c[x]+=a; 9 x+=(x&-x);10 }11 return;12 }13 14 int sum(int x){15 int t=0;16 while(x){17 t+=c[x];18 x-=(x&-x);19 }20 return t;21 }22 23 int main(){24 int T;25 while(scanf("%d",&T)!=EOF){26 for(int q=1;q<=T;q++){27 printf("Case %d:\n",q);28 memset(c,0,sizeof(c));29 scanf("%d",&N);30 int i,t;31 for(i=1;i<=N;i++){32 scanf("%d",&t);33 add(i,t);34 }35 char s[10];36 while(scanf("%s",s)){37 // printf("%s\n",s);38 if(s[0]=='S'){39 scanf("%d%d",&i,&t);40 add(i,-t);41 }42 else if(s[0]=='A'){43 scanf("%d%d",&i,&t);44 add(i,t);45 }46 else if(s[0]=='Q'){47 scanf("%d%d",&i,&t);48 printf("%d\n",sum(t)-sum(i-1));49 }50 else if(s[0]=='E')break;51 }52 }53 }54 return 0;55 }
1 #include2 #include 3 const int maxm=50005; 4 5 char s[10]; 6 int a[maxm],st[maxm<<2]; 7 8 void build(int o,int l,int r){ 9 if(l==r){10 st[o]=a[l];11 return;12 }13 int m=l+((r-l)>>1);14 build(o<<1,l,m);15 build(o<<1|1,m+1,r);16 st[o]=st[o<<1]+st[o<<1|1];17 }18 19 void update(int o,int l,int r,int x,int c){20 if(l==r){21 st[o]+=c;22 return;23 }24 int m=l+((r-l)>>1);25 if(x<=m)update(o<<1,l,m,x,c);26 if(x>=m+1)update(o<<1|1,m+1,r,x,c);27 st[o]=st[o<<1]+st[o<<1|1];28 }29 30 int query(int o,int l,int r,int ql,int qr){31 if(ql<=l&&qr>=r)return st[o];32 int m=l+((r-l)>>1);33 int ans=0;34 if(ql<=m)ans+=query(o<<1,l,m,ql,qr);35 if(qr>=m+1)ans+=query(o<<1|1,m+1,r,ql,qr);36 return ans;37 }38 39 int read(){40 int x=0;41 char c=getchar();42 while(c>'9'||c<'0')c=getchar();43 while(c>='0'&&c<='9'){44 x=x*10+c-'0';45 c=getchar();46 }47 return x;48 }49 50 51 int main(){52 int T=read();53 for(int q=1;q<=T;q++){54 int n=read();55 int i;56 for(i=1;i<=n;i++)a[i]=read();57 build(1,1,n);58 printf("Case %d:\n",q);59 while(1){60 scanf("%s",s);61 if(s[0]=='Q'){62 int ql=read();63 int qr=read();64 printf("%d\n",query(1,1,n,ql,qr));65 }66 else if(s[0]=='A'){67 int x=read();68 int c=read();69 update(1,1,n,x,c);70 }71 else if(s[0]=='S'){72 int x=read();73 int c=read();74 update(1,1,n,x,-c);75 }76 else if(s[0]=='E')break;77 }78 }79 return 0;80 }