树状数组（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 }

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢