树状数组学习笔记

>>搞懂树状数组：http://blog.csdn.net/int64ago/article/details/7429868

据说可以用树状数组的解决的问题都可以用线段树解决，所以下面的题都是可以用线段树解决的。

一维树状数组应用：

我用到的模版表示：

View Code 
 1 #define MAXN 32005
 2 
 3 int sum[MAXN];
 4 
 5 int lowbit(int x)
 6 {
 7     return x&(-x);
 8 }
 9 
10 void update(int x,int val)////如果要把a[i]增加v，可以通过调用如下函数实现
11 {
12     while(x <= MAXN)
13     {
14         sum[x] += val;
15         x += lowbit(x);//x+lowbit(x)可以理解变成了x的父亲
16     }
17 }
18 
19 int query(int x)//前x项和
20 {
21     int s=0;
22     while(x>0)
23     {
24         s += sum[x];
25         x -= lowbit(x);//x-lowbit(x)可以理解成变成了x的兄弟
26     }
27     return s;
28 }

1，区间求和

poj-2352:

题意：一个“*”的层次是这样定义的，处于该“*”的下面和左面的范围内的“*”的个数即为该“*”的层次。题目要求处于0到n-1层次的“*”数目各有几个。

分析：由于“*”的坐标已经按Y递增的顺序排列好，对于具有相同Y坐标的“*”，又按其X坐标排序，故可充分利用这一输入特点，直接运用树状数组进行求解。

View Code 
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 #define MAXN 32005
 7 
 8 int sum[MAXN],ans[MAXN];
 9 
10 int lowbit(int x)
11 {
12     return x&(-x);
13 }
14 
15 void update(int x,int val)
16 {
17     while(x <= MAXN)
18     {
19         sum[x] += val;
20         x += lowbit(x);
21     }
22 }
23 
24 int query(int x)//前x项和
25 {
26     int s=0;
27     while(x>0)
28     {
29         s += sum[x];
30         x -= lowbit(x);
31     }
32     return s;
33 }
34 
35 int main()
36 {
37     int n;
38     while(scanf("%d",&n) != EOF)
39     {
40         int x,y;
41         memset(sum,0,sizeof(sum));
42         memset(ans,0,sizeof(ans));
43         for(int i=0;i<n;i++)
44         {
45             scanf("%d%d",&x,&y);
46             ans[query(x+1)]++;//x+1避免死循环,每次插入前查询小于x的和，
47             update(x+1,1);
48         }
49         for(int i=0;i<n;i++)
50             printf("%d\n",ans[i]);
51     }
52     return 0;
53 }

2，查找第K小或大（第k大可以转化成num-k+1小元素）元素：

poj-2985:

题意：有一群猫，现在给它们编号，然后组队，0 1 2 代表 1 号和 2 号的队伍合并。 1 4 询问第 4 大的队伍 Size 是多大。

分析：并查集处理集合，动态更新第K值用树状数组，具体的看注释

时间复杂度是：log(n)^2

View Code 
 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 #define MAXN 300000
 7 
 8 int rank[MAXN],sum[MAXN],fa[MAXN];//rank表示集合的大小，初始为1
 9 
10 int lowbit(int x)
11 {
12     return x&(-x);
13 }
14 
15 void update(int x,int d)
16 {
17     while(x<=MAXN)
18     {
19         sum[x]+=d;//d=1或-1
20         x+=lowbit(x);
21     }
22 }
23 
24 int query(int x)
25 {
26     int s=0;
27     while(x>0)
28     {
29         s+=sum[x];
30         x-=lowbit(x);
31     }
32     return s;
33 }
34 
35 int find(int x)
36 {
37     if(x!=fa[x])
38         fa[x]=find(fa[x]);
39     return fa[x];
40 }
41 
42 int main()
43 {
44     int i,n,m,q,x,y,k,l,r;
45     scanf("%d%d",&n,&m);
46     for(int i=1;i<=n;i++)
47     {
48         fa[i]=i;
49         rank[i]=1;
50     }
51     update(1,n);//初始状态值为1的有n个，（用线段树的思想理解就是第1-r这个区间都有1个值）
52     int num=n;
53 
54     for(i=1;i<=m;i++)
55     {
56         scanf("%d",&q);
57         if(q==0)
58         {
59             scanf("%d%d",&x,&y);
60             x=find(x);
61             y=find(y);
62             if(x==y) continue;
63             update(rank[x],-1);//即将集合大小为rank[x]的总数减1，在树状数组上表示为和-1
64             update(rank[y],-1);
65             update(rank[x]+rank[y],1);
66             fa[y]=x;
67             rank[x]+=rank[y];
68             num--;
69         }
70         else
71         {
72             scanf("%d",&k);
73             k=num-k+1;//转换成求k小
74             l=1;
75             r=n;
76             while( l <= r)//二分逼近求k小，跟线段树类似
77             {
78                 int m=(l+r)>>1;
79                 if(query(m) >= k)
80                     r=m-1;//query(m)是前m的和，大于k表明在前1-m这段有大于k个值存在，即k应小于m
81                 else
82                     l=m+1;
83             }
84             printf("%d\n",l);
85         }
86     }
87     return 0;
88 }

另外贴一个时间复杂度是log(n)的写法，看这里

View Code
 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 300000
 4 int a[maxn],c[maxn],p[maxn];//值为i的数有i个
 5 int find(int x){return x==p[x] ? x : p[x]=find(p[x]);}
 6 int lowbit(int x){
 7     return x&-x;
 8 }
 9 void update(int x,int d){
10     for(;x<=maxn;x+=lowbit(x))
11         c[x]+=d;
12 }//因为是从左往右手动求和了，所以也不需要sum()操作了
13 int find_kth(int k)//太神奇了(大概是以前没有完全领会)，log(n)复杂度
14 {
15     int ans = 0, cnt = 0, i;
16     for (i = 20; i >= 0; i--)//利用二进制的思想，把答案用一个二进制数来表示
17     {
18         ans += (1 << i);
19         if (ans >= maxn|| cnt + c[ans] >= k)
20             //这里大于等于k的原因是可能大小为ans的数不在c[ans]的控制范围之内，所以这里求的是 < k
21             ans -= (1 << i);
22         else
23             cnt += c[ans];//cnt用来累加比当前ans小的总组数
24     }//求出的ans是累加和（即小于等于ans的数的个数）小于k的情况下ans的最大值，所以ans+1就是第k大的数
25     return ans + 1;
26 }
27 /*
28 因为要求第k小的数，所以要从左往右加过去，
29 上述过程其实就是把树状数组的求和操作逆向，从左往右求和，
30 边求和边判断控制范围内比当前值要小的数是否超过或等于k,如果是则跳回兄弟节点(ans-=(1<<i))
31 如8+4=12，假如12不满足要求，则重新变回8，下一次就加2,8+2=10，即跳到10控制的位置
32 上述累加过程不会重复计算，因为
33 比如15=8+4+2+1，数字依次为8  12  14  15，每次累加后的值都与前面的值无关，i小于其二进制末尾0的个数
34 即c[8] 、c[12] 、c[14]、 c[15]相加的话不会重复计算，再如11=8+2+1;数字依次为8 10 11，c[8],c[10],c[11]
35 各自控制着自己的范围，不会重复累加，所以就可以用cnt来累加前面的结果，最后cnt+c[ans]就表示了值<=ans的个数
36 简言之：上述的各个数字两两间控制的范围不会相交
37 */
38 int main()
39 {
40     int i,n,m,q,x,y,k,l,r;
41     scanf("%d%d",&n,&m);
42     for(i=1;i<=n;i++) p[i]=i;
43     for(i=1;i<=n;i++) a[i]=1;
44     update(1,n);//初始状态值为1的数有n个
45     int num=n;
46     for(i=1;i<=m;i++)
47     {
48         scanf("%d",&q);
49         if(q==0)
50         {
51             scanf("%d%d",&x,&y);
52             x=find(x);
53             y=find(y);
54             if(x==y) continue;
55             update(a[x],-1);
56             update(a[y],-1);
57             update(a[x]+a[y],1);
58             p[y]=x;
59             a[x]+=a[y];
60             num--;//合并集合
61         }
62         else 
63         {
64             scanf("%d",&k);
65             k=num-k+1;//转换为找第k小的数
66             printf("%d\n",find_kth(k));
67         }
68     }
69     return 0;
70 }

PS:其他方法查询第K小元素看这里

3，求逆序数

首先使用query(x)查询比x小的数出现了几个，然后update(x,1)把x更新进去。
比如
4 3 1 2
i=0 : query(4)==0(说明比4小的数还未出现),那么当前ans+= i-query(4);

update(4,1);

i=1 : query(3)==0, ans+=i-query(3)->ans=1;

update(3,1);

。。。。

i-query()可以这样理解：本来第i个数出现时，假如没有逆序数，则query(x)应该返回i即前面的数都在x前面，但是只返回query(x)，故还有i-query(x)个数大于x且出现的早于x.即产生的逆序数对。

poj-3067

题意：有两排城市，这两排之间有一些城市之间有连接的道路，给出所有道路，问有多少道路是相交的。

分析：求逆序数。我们先把所有的道路按照a升序，a相同时b升序的方法排列。这样从头至尾便利，对于每条道路，我们只需要知道它之前有多少道路的b大于等于它的b就可以了，所以我们只要知道前面有多少b小于它的再用下标减去就可以了。而这个求有多少小于的过程就用树状数组来实现。我们每看到一条边，就把它的b作为下标，把树状数组对应位进行修改。这样一来，树状数组所有下标小于该道路的b的数的总和就是我们要求的b小于该道路的道路数。(自己画个图便于理解)

 

View Code 
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define MAXN 2005
 8 int N,M,K;
 9 long long ans;
10 struct ci
11 {
12     int e,w;
13     bool operator <(const ci & a) const
14     {
15         if(e==a.e)
16             return w<a.w;
17         return e<a.e;
18     }
19 }line[MAXN * MAXN];
20 int sum[MAXN];
21 int lowbit(int x)
22 {
23     return x&(-x);
24 }
25 
26 void update(int x,int val)
27 {
28     while(x <= MAXN)
29     {
30         sum[x] += val;
31         x += lowbit(x);
32     }
33 }
34 
35 long long query(int x)
36 {
37     long long s=0;
38     while(x>0)
39     {
40         s += sum[x];
41         x -= lowbit(x);
42     }
43     return s;
44 }
45 
46 int main()
47 {
48     int t;
49     int set=1;
50     scanf("%d",&t);
51     while(t--)
52     {
53         ans=0;
54         memset(sum,0,sizeof(sum));
55         scanf("%d%d%d",&N,&M,&K);
56         for(int i=0;i<K;i++)
57             scanf("%d%d",&line[i].e,&line[i].w);
58         sort(line,line+K);
59         for(int i=0;i<K;i++)
60         {
61             ans+=i-query(line[i].w);
62             update(line[i].w,1);
63         }
64         printf("Test case %d: %I64d\n",set++,ans);
65     }
66     return 0;
67 }

PS:求逆序数还有归并排序，当然线段树也行。

 二维树状数组：

+++还没看的...

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Missa/p/2628043.html