Posted on 2007-08-26 02:29
魔のkyo 阅读(912)
评论(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;
}
};