付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
http://acm.hdu.edu.cn/showproblem.php?pid=1166

对于详细的树状数组的介绍 可以百度 有很多相关的资料

#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++)//树状数组初始化
        {
            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 付翔 阅读(255) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜