http://acm.hdu.edu.cn/showproblem.php?pid=1166對(duì)于詳細(xì)的樹狀數(shù)組的介紹 可以百度 有很多相關(guān)的資料
#include<iostream>
using namespace std;
const int maxn = 50010;
//long data[maxn];
long result[maxn];
long n;
int Lowbit(int t)
{
//return t & ( t ^ ( t - 1 ) );
return (-t)&t;
}
int Sum(int end)
{
long sum = 0;
while(end > 0)
{
sum += result[end];
end -= Lowbit(end);
}
return sum;
}
void plus(int pos , int num)
{
while(pos <= n)
{
result[pos] += num;
pos += Lowbit(pos);
}
}
int main()
{
//freopen("out.txt","w",stdout);
int casenum,i,case1,a,b;
long num;
char str[100];
cin>>casenum;
case1 = 1;
while(casenum--)
{
//memset(data,0,sizeof(data));
memset(result,0,sizeof(result));
cin>>n;
for(i = 1; i <= n;i++)//樹狀數(shù)組初始化
{
cin>> num;
plus(i,num);
}
printf("Case %d:\n",case1);
while(cin>>str,strcmp(str,"End")!=0)
{
cin>>a>>b;
if(strcmp(str,"Query")==0)
printf("%ld\n",Sum(b) - Sum(a-1));
else if(strcmp(str,"Add")==0)
plus(a,b);
else if(strcmp(str,"Sub")==0)
plus(a,0-b);
}
case1 ++;
}
return 0;
}
posted on 2010-04-29 14:04
付翔 閱讀(258)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM 數(shù)據(jù)結(jié)構(gòu)