此題是第三次AC了。第一次高二的時候剛開始學(xué)線段樹，然后前端時間復(fù)習(xí)線段樹，然后就是這次用樹狀數(shù)組實現(xiàn)。
以下是我的代碼：
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#define lowbit(x) ((x)&(-(x))) // 2^k
using namespace std;
const int kMaxn(50007);
int n,bit[kMaxn];
void Add(int pos,int delta)
{
while(pos<=n)
{
bit[pos]+=delta;
pos+=lowbit(pos);
}
}
int Sum(int pos)
{
int re(0);
while(pos>0)
{
re+=bit[pos];
pos-=lowbit(pos);
}
return re;
}
int main()
{
int T;
scanf("%d",&T);
for(int case_num=1;case_num<=T;case_num++)
{
scanf("%d",&n);
memset(bit,0,sizeof(bit));
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
Add(i,t);
}
printf("Case %d:\n",case_num);
string cmd;
while(cin>>cmd && cmd!="End")
{
if(cmd=="Add")
{
int a,b;
scanf("%d%d",&a,&b);
Add(a,b);
}
else if(cmd=="Sub")
{
int a,b;
scanf("%d%d",&a,&b);
Add(a,-b);
}
else if(cmd=="Query")
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",Sum(b)-Sum(a-1));
}
}
}
return 0;
}
posted on 2011-07-31 09:22
lee1r 閱讀(285)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結(jié)構(gòu)