树状数组模版

原来听到树状数组这名字感觉很难，很高大上。学了一下发现不难。而且很好。

普通的数组修改某个值耗费为O(1),输出和为O(n);而树状数组为O(logn);
lowbit（x）
{
　　return x&(-x);
}
返回的是x二进制最后一位1的位置;

有公式:cn=a(n-a^k+1)+.........+an（其中 k 为 n 的二进制表示中从右往左数的 0 的个数）。

模版

 1 #include<stdio.h>
 2 #include<string.h>
 3 int a[1000],n;
 4 int lowbit(int x)
 5 {
 6     return x&(-x);
 7 }
 8 void update(int i,int val)
 9 {
10     while(i<=n)
11     {
12         a[i]+=val;
13         i+=lowbit(i);
14     }
15 }
16 int Sum(int i)
17 {
18     int sum=0;
19     while(i>0)
20     {
21         sum+=a[i];
22         i-=lowbit(i);
23     }
24     return sum;
25 }
26 int main()
27 {
28     int i,j;
29     while(scanf("%d",&n)!=EOF)
30     {
31         for(i=1;i<=n;i++)
32         {
33             int val;
34             scanf("%d",&val);
35             update(i,val);
36         }
37         for(i=1;i<=n;i++)
38             printf("%d ",a[i]);
39         printf("
");
40         int ans=Sum(3);
41         printf("%d
",ans);
42         //update(1,3);
43         //ans=Sum(3);
44         //printf("%d
",ans);
45     }
46 }

View Code

hdu1166入门

 1 //hdu1166入门
 2 #include<stdio.h>
 3 #include<string.h>
 4 int c[50005],n,a[50005];
 5 char s[100];
 6 int lowbit(int x)
 7 {
 8     return x&(-x);
 9 }
10 void add(int i,int val)
11 {
12     int j;
13     while(i<=n)
14     {
15         c[i]+=val;
16         i+=lowbit(i);
17     }
18 }
19 void sub(int i,int val)
20 {
21     int j;
22     while(i<=n)
23     {
24         c[i]-=val;
25         i+=lowbit(i);
26     }
27 }
28 int Sum(int i)
29 {
30     int sum=0;
31     while(i>0)
32     {
33         sum+=c[i];
34         i-=lowbit(i);
35     }
36     return sum;
37 }
38 int main()
39 {
40     int i,j,t,ff=0;
41     scanf("%d",&t);
42     while(t--)
43     {
44         memset(c,0,sizeof(c));
45         scanf("%d",&n);
46         for(i=1;i<=n;i++)
47         {
48             int exm;
49             scanf("%d",&exm);
50             add(i,exm);
51         }
52         printf("Case %d:
",++ff);
53         while(1)
54         {
55             scanf("%s",s);
56             if(s[0]=='A')
57             {
58                 int x,y;
59                 scanf("%d%d",&x,&y);
60                 add(x,y);
61             }
62             else if(s[0]=='Q')
63             {
64                 int setf,sett;
65                 scanf("%d%d",&setf,&sett);
66                 int ans1=Sum(setf-1);
67                 int ans2=Sum(sett);
68                 printf("%d
",ans2-ans1);
69             }
70             else if(s[0]=='S')
71             {
72                 int del,val;
73                 scanf("%d%d",&del,&val);
74                 sub(del,val);
75             }
76             else if(s[0]=='E')
77             {
78                 break;
79             }
80         }
81     }
82 }

View Code