posts - 217, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

树状数组Binary Indexed Tree

Posted on 2007-08-26 02:29 魔のkyo 阅读(833) 评论(0)  编辑 收藏 引用 所属分类: DataStucture
//Binary Indexed Tree
//以O(logn)的时间完成修改项,查询前n项和

template 
<int N>//表示可用区间为[1,N],其中N必须是2的幂
class BITree{
    
int C[N+1];
    
int lowbit(int i)
    {
        
return i&(-i);
    }
public:
    BITree(){memset(C,
0,sizeof(C));}
    
void clear(){memset(C,0,sizeof(C));}

    
void modify(int i,int d)
    {
        
while(i<=N){
            C[i]
+=d;
            i
+=lowbit(i);
        }
    }
    
    
//返回sum[i]=sum{a1,a2,,ai}
    int operator [] (int i)
    {
        
int sum=0;
        
while(i){
            sum
+=C[i];
            i
-=lowbit(i);
        }
        
return sum;
    }
};
只有注册用户登录后才能发表评论。