树状数组
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 |
#include <cstdio>#include <cstring>using
namespace std;const
int N=50010;int T,n,cnt=1,x,y;char
s[6];int c[N];void
init(){for(int
i=0;i<N;i++)c[i]=0;}void
add(int
x,int num){while(x<=n)c[x]+=num,x+=x&-x;}int
sum(int
x){int
s=0;while(x>0)s+=c[x],x-=x&-x;return
s;}int
main(){ scanf("%d",&T); while(T--){ init(); scanf("%d",&n); for(int
i=1;i<=n;i++){scanf("%d",&x);add(i,x);} printf("Case %d:\n",cnt++); while(scanf("%s",s),strcmp(s,"End")){ scanf("%d%d",&x,&y); if(strcmp(s,"Add")==0)add(x,y); else
if(strcmp(s,"Sub")==0)add(x,-y); else
printf("%d\n",sum(y)-sum(x-1)); } } return
0;} |
线段树
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 |
#include <cstdio> #include <cstring>const
int N=60000;int T,n,cnt=1,x,y,sum[N<<2];char
s[6];void
init(){for(int
i=1;i<N*4;i++)sum[i]=0;}void
up(int
x){sum[x]=sum[x<<1]+sum[x<<1|1];}void
build(int
l,int r,int x){ if(l==r){scanf("%d",&sum[x]);return;} int
mid=(l+r)>>1; build(l,mid,x<<1); build(mid+1,r,x<<1|1); up(x);//注意不要漏写}void
update(int
t,int num,int
l,int r,int x){ if(l==r){sum[x]+=num;return;} int
mid=(l+r)>>1; if(t<=mid)update(t,num,l,mid,x<<1); else
update(t,num,mid+1,r,x<<1|1); up(x);//同上}int
query(int
L,int R,int l,int r,int x){ if(L<=l&&r<=R){return
sum[x];} int
mid=(l+r)>>1,tmp=0; if(L<=mid)tmp+=query(L,R,l,mid,x<<1); if(R>mid)tmp+=query(L,R,mid+1,r,x<<1|1); return
tmp;}int
main(){ scanf("%d",&T); while(T--){ init(); printf("Case %d:\n",cnt++); scanf("%d",&n); build(1,n,1); while(scanf("%s",s),strcmp(s,"End")){ scanf("%d%d",&x,&y); if(strcmp(s,"Add")==0)update(x,y,1,n,1); else
if(strcmp(s,"Sub")==0)update(x,-y,1,n,1); else
printf("%d\n",query(x,y,1,n,1)); } } return
0;} |
原文：http://www.cnblogs.com/forever97/p/3567504.html