i的二进制的最后一个1可以通过i&(-i)得到，时间复杂度o(logn)。对于W*H的二维BIT只需要建立H个大小为x轴方向元素个数W的BIT，复杂度O(logW+logH)。同样的方法可以扩展到更高维度的情况。
1 int sum(int i) 2 { 3 int s=0; 4 while(i>0) { 5 s+=bit[i]; 6 i-=i&(-i); 7 } 8 return s; 9 } 10 void add(int i,int x) 11 { 12 while(i<=n) { 13 bit[i]+=x; 14 i+=i&(-i); 15 } 16 } 17 18 int main() 19 { 20 int x,y; 21 scanf("%d%d",&n,&m); 22 for(int i=1;i<=n;i++) { 23 scanf("%d",&a[i]); 24 add(i,a[i]); 25 } 26 while(m--) { 27 scanf("%d",&x); 28 printf("%d\n",sum(x));//前x项和 29 } 30 31 return 0; 32 }
原文：http://www.cnblogs.com/sxiszero/p/4348870.html