树状数组（BIT）
浏览数：20 /
时间：2015年06月08日
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 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
