树状数组(BIT)

i的二进制的最后一个1可以通过i&(-i)得到,时间复杂度o(logn)。对于W*H的二维BIT只需要建立H个大小为x轴方向元素个数W的BIT,复杂度O(logW+logH)。同样的方法可以扩展到更高维度的情况。

 int sum(int i)
{
int s=;
while(i>) {
s+=bit[i];
i-=i&(-i);
}
return s;
}
void add(int i,int x)
{
while(i<=n) {
bit[i]+=x;
i+=i&(-i);
}
} int main()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) {
scanf("%d",&a[i]);
add(i,a[i]);
}
while(m--) {
scanf("%d",&x);
printf("%d\n",sum(x));//前x项和
} return ;
}
上一篇:redis cluster集群web管理工具 relumin


下一篇:css3 3d变换和动画——回顾