心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
此题是第三次AC了。第一次高二的时候刚开始学线段树,然后前端时间复习线段树,然后就是这次用树状数组实现。
以下是我的代码:
#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 阅读(265) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

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