hdu 1166 树状数组模板题

#include<stdio.h>

#include<string.h>

#define N 51000

int c[N],n;

int number(int x) {

return x&-x;

}

void creat(int a,int x) {

int i;

for(i=a;i<=n;i+=number(i))

c[i]+=x;

}

int sum(int x) {

int h=0,i;

for(i=x;i>0;i-=number(i))

h+=c[i];

return h;

}

int bsum(int x,int y) {

return sum(y)-sum(x);

}

int main() {

int i,j,t,k,count=0;

char s[30];

scanf("%d",&t);

while(t--) {

scanf("%d",&n);

memset(c,0,sizeof(c));

for(i=1;i<=n;i++) {

scanf("%d",&k);

creat(i,k);

}

printf("Case %d:\n",++count);

while(scanf("%s",s),strcmp(s,"End")) {

if(s[0]=='Q') {

scanf("%d%d",&i,&j);

printf("%d\n",bsum(i-1,j));

}

else

if(s[0]=='A'){

scanf("%d%d",&i,&k);

creat(i,k);

}

else

if(s[0]=='S'){

scanf("%d%d",&i,&k);

creat(i,-k);

}

}

}

return 0;

}

巴特西

hdu 1166 树状数组模板题

最新文章

热门文章