hdu 1166 敌兵布阵（树状数组）

题意：区间和

思路：树状数组

#include

#include

#include

using namespace std;

int n,c[50005];

int lowbit(int i){

return i&-i;

}

void update(int i,int val){//更新函数

while(i<=n){//注意这个n的变化，应该为最大值，具体题目自行变化。

c[i]+=val;

i+=lowbit(i);

}

}

int sum(int i){//求和函数

int sum=0;

while(i>0){

sum+=c[i];

i-=lowbit(i);

}

return sum;

}

int main(){

int t,a,b,i,j;

char str[10];

scanf("%d",&t);

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

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

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

scanf("%d",&n);

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

scanf("%d",&b);

update(j,b);

}

while(~scanf("%s",str)&&str[0]!='E'){

scanf("%d%d",&a,&b);

if(str[0]=='A')update(a,b);

else if(str[0]=='S')update(a,-b);

else printf("%d\n",sum(b)-sum(a-1));

}

}

return 0;

}

View Code

参考阅读