树状数组总结

树状数组还是挺方便的，代码短功能也强大，完全可以用来替代一部分线段树的功能

有三种用法

一是对于单点更新，区间查询的

 1 //hdu 1166
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 int n,t;
 9 int a[50008];
10 int tree[50008];
11 
12 void add(int x,int num)
13 {
14     while(x<=n)
15     {
16         tree[x]+=num;
17         x+=x&-x;
18     }
19 }
20 
21 int read(int x)
22 {
23     int sum = 0;
24     while(x)
25     {
26         sum+=tree[x];
27         x-=x&-x;
28     }
29     return sum;
30 }
31 
32 int main()
33 {
34     string tmp;
35     int b,c;
36     scanf("%d",&t);
37     for(int j = 1;j<=t;j++)
38     {
39         memset(tree,0,sizeof(tree));
40         scanf("%d",&n);
41         printf("Case %d:
",j);
42         for(int i = 1;i<=n;i++)
43         {
44              scanf("%d",&a[i]);
45              add(i,a[i]);
46         }
47 
48         while(cin>>tmp,tmp!="End")
49         {
50             if(tmp=="Query")
51             {
52                 scanf("%d%d",&b,&c);
53                 printf("%d
",read(c)-read(b-1));
54             }else if(tmp=="Add")
55             {
56                 scanf("%d%d",&b,&c);
57                 add(b,c);
58             }else if(tmp=="Sub")
59             {
60                 scanf("%d%d",&b,&c);
61                 add(b,-c);
62             }
63         }
64     }
65     return 0;
66 }

二是对于单点更新，但是查询区间最大最小值的

 1 //hdu 1754
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 int n,m;
 9 int a[200008];
10 int tree[200008];
11 
12 int lowbit(int x)
13 {
14     return x&-x;
15 }
16 
17 void update(int x)
18 {
19     while(x<=m)
20     {
21         tree[x]=a[x];
22         for(int i=1;i<lowbit(x);i<<=1)
23             tree[x]=max(tree[x],tree[x-i]);
24         x+=lowbit(x);
25     }
26     return ;
27 }
28 int query(int x, int y)
29 {
30     int ans = 0;
31     while (y >= x)
32     {
33         ans = max(a[y], ans);
34         y --;
35         for (; y-lowbit(y) >= x; y -= lowbit(y))
36             ans = max(tree[y], ans);
37     }
38     return ans;
39 }
40 
41 int main()
42 {
43     char tmp;
44     int c,d;
45     while(scanf("%d%d",&m,&n)!=EOF)
46     {
47         memset(tree,0,sizeof(tree));
48         for(int i = 1;i<=m;i++)
49         {
50             scanf("%d",&a[i]);
51             update(i);
52         }
53         getchar();
54         for(int i = 1 ;i <= n;i++)
55         {
56             scanf("%c%d%d",&tmp,&c,&d);
57             if(tmp=='U')
58             {
59                 a[c] = d;
60                 update(c);
61             }
62             else if(tmp=='Q')
63             {
64                 printf("%d
",query(c,d));
65             }
66             getchar();
67         }
68     }
69     return 0;
70 }

三是对于区间更新，然后区间查询

这个区间更新主要是要用到一个差分数组

我们假设sigma(r，i)表示r数组的前i项和，调用一次的复杂度是log2(i)

设原数组是a[n]，差分数组c[n]，c[i]=a[i]-a[i-1]，那么明显地a[i]=sigma(c,i)，如果想要修改a[i]到a[j](比如+v)，只需令c[i]+=v,c[j+1]-=v

这样c[i]->C[j]便会相当与加了j-i个v

怎么实现“区间修改，区间查询”呢？

观察式子：
a[1]+a[2]+...+a[n]

= (c[1]) + (c[1]+c[2]) + ... + (c[1]+c[2]+...+c[n])

= n*c[1] + (n-1)*c[2] +... +c[n]

= n * (c[1]+c[2]+...+c[n]) - (0*c[1]+1*c[2]+...+(n-1)*c[n])

那么我们就维护一个数组c2[n]，其中c2[i] = (i-1)*c[i]

每当修改c的时候，就同步修改一下c2，这样复杂度就不会改变

那么

式子①

=n*sigma(c,n) - sigma(c2,n)

于是我们做到了在O(logN)的时间内完成一次区间和查询

 1 //poj 3468
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <iostream>
 5 #define Nmax 200008
 6 
 7 using namespace std;
 8 
 9 int n,m;
10 long long a[200008];
11 long long tree[200008];
12 long long sum[200008];    //原始的前缀合
13 long long c1[Nmax];   //前缀和
14 long long c2[Nmax];   //前缀和*i-1
15 
16 int lowbit(long long x)
17 {
18     return x&-x;
19 }
20 
21 void add(long long *array,long long x,long long num)
22 {
23     while(x<=n)
24     {
25         array[x] += num;
26         x+=x&-x;
27     }
28 }
29 
30 
31 long long read(long long *array,long long x)
32 {
33     long long sum = 0;
34     while(x)
35     {
36         sum += array[x];
37         x-=x&-x;
38     }
39     return sum;
40 }
41 
42 int main()
43 {
44     scanf("%d%d",&n,&m);
45     char tmp;
46     long long  l,r,q;
47     for(int i = 1;i<=n;i++)
48     {
49         scanf("%lld",&a[i]);
50         add(c1,i,a[i]-a[i-1]);
51         add(c2,i,(i-1)*(a[i]-a[i-1]));
52     }
53     getchar();
54     for(int i = 1;i<=m;i++)
55     {
56         scanf("%c",&tmp);
57         if(tmp=='C')
58         {
59             scanf("%lld%lld%lld",&l,&r,&q);
60             add(c1,l,q);
61             add(c1,r+1,-q);
62             add(c2,l,(l-1)*q);
63             add(c2,r+1,-q*r);
64         }else if(tmp=='Q')
65         {
66             scanf("%lld%lld",&l,&r);
67             long long ans1 = (l-1)*read(c1,l-1)-read(c2,l-1);
68             long long ans2 = (r)*read(c1,r)-read(c2,r);
69             printf("%lld
",ans2-ans1);
70         }
71         getchar();
72     }
73     return 0;
74 }

四、利用树状数组来求第k小或者第k大

其主要的想法就是利用树状数组来统计每个数出现的次数

然后在通过枚举二进制的方式来进行统计，复杂度是log(n)

详情看代码理解

这个代码是第K大的，如果要求第K小的，那么枚举的时候反过来即可，以及判断条件改一下就OK

如果想取第几名的话，那么改插入的条件，每个值只能插入一次即可。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define maxn 100000
 4 
 5 int tree[maxn],n,k;    //tree是统计次数，每个数字出现的次数
 6 
 7 int lowbit(int x)
 8 {
 9     return x&-x;
10 }
11 
12 void add(int x, int num)
13 {
14     while (x <= maxn)
15     {
16         tree[x] += num;
17         x += lowbit(x);
18     }
19 }
20 
21 int find(int k)     //找第k大
22 {
23     int cnt = 0, ans = 0;
24     for (int i = 20; i >= 0; i--)       //枚举二进制数
25     {
26         ans += (1 << i);
27         if (ans >= maxn|| cnt + tree[ans] >= k)     //如果ans超过最大值或者累加值加起来超过了k，那么说明这个位置的肯定在k的后面
28             ans -= (1 << i);
29         else
30             cnt += tree[ans];     //说明第k肯定在ans的后面
31     }
32     return ans + 1;
33 }
34 
35 void input() {
36     memset(tree, 0, sizeof(tree));
37     int t;
38     scanf("%d%d", &n, &k);
39     for (int i = 0; i<n; i++) {
40         scanf("%d", &t);
41         add(t, 1);                       //t位置的次数加一
42     }
43     printf("%d/n", find(k));
44 }