?

樹狀數組應用：

我理解這個怎么更新最值問題也想了很久，我認為要完全理解樹狀數組的應用要理解透兩點：

1.lowbit（i）是干什么用的。

2.c[i]是怎么保存狀態的。

• 區間求和類問題（前綴和）
• 最大值/最小值
• 求序列中第 K 大數
• “圖騰”類問題的統計

1.區間求和類問題（前綴和）上面講了，就不舉例了；

?

2.最大值/最小值（最大最小一樣，改個max）

for(int x=1; x<lowbit(i); x<<=1)
?{
?? ???c[i]=max(c[i],c[i-x]);
?}

對于c[i]，每次都是往下更新最值的。而i是根據lowbit的規則往下的。舉例：

lowbit(8)=8;

i==4，c[i-1]=c[7];? x<<=1==2;??

? ? ? ? ? ?c[i-2]=c[6],? x<<=1==4;

? ? ? ? ? ?c[i-4]=c[4],? x<<=1=8;

break;

說明每次c[i]都是把它的子樹或者節點更新，若它的子樹的最大值大于當前的值，則更新；

hdu1754AC代碼

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}const int maxn=2e5+10;int n,m,a[maxn],c[maxn];int lowbit(int x) {return x&(-x); } void update(int i,int value) {while(i<=n){c[i]=value;for(int x=1; x<lowbit(i); x<<=1){c[i]=max(c[i],c[i-x]);}i+=lowbit(i);}return ; } int query(int l,int r) {int ans=0;while(l<=r){ans=max(ans,a[r]);r--;for(; r-l>=lowbit(r); r-=lowbit(r)){ans=max(ans,c[r]);}}return ans; } int main() {while(~scanf("%d%d",&n,&m)){for(int i=1; i<=n; i++)c[i]=0;for(int i=1; i<=n; i++){scanf("%d",&a[i]);update(i,a[i]);}while(m--){char s[5];int x,y;scanf("%s %d%d",s,&x,&y);if(s[0]=='Q'){printf("%d\n",query(x,y));}else{a[x]=y;update(x,y);}}}return 0; }

3.求序列中第 K 大數

以POJ 2985為例，具體的寫在程序里。思路都是基于二分的思想。

下面是(LogN)^2的方法

? /*題意：某人養了很多貓，他會把一些貓合并成一組，并且會詢問第k大組有幾只貓算法：處理集合用并查集，動態更新第K值用樹狀數組，具體的看注釋2011-07-21 19:59 */#include <stdio.h>#define MAXN 300000int a[MAXN], f[MAXN],c[MAXN];//c[maxn]表示值為i的數有i個； int n, m;int lowbit(int x) {return x & -x; }int find(int x) {if (x != f[x])f[x] = find(f[x]);return f[x]; }void add(int x, int num) {for ( ; x <= n; x += lowbit(x))c[x] += num; }int sum(int x) {int sum = 0;for ( ; x > 0; x -= lowbit(x))sum += c[x];return sum; }int main() {int i, num, cmd, x, y, k, l, r;scanf("%d%d", &n, &m);for (i = 1; i <= n; i++)f[i] = i;for (i = 1; i <= n; i++)a[i] = 1;add(1, n);//初始狀態值為1的數有n個， a[i]表示組內有i只貓的組數，num = n;for (i = 1; i <= m; i++){scanf("%d", &cmd);if (cmd == 0){scanf("%d%d", &x, &y);x = find(x);y = find(y);if (x == y)continue;add(a[x], -1);add(a[y], -1);add(a[y] = a[x] + a[y], 1);f[x] = y;num--;//合并集合}else{scanf("%d", &k);k = num - k + 1;//轉換為找第k小的數l = 1;r = n;//二分逼近求第k大值，就是求第num - k + 1小的值while (l <= r){int mid = (l + r) / 2;if (sum(mid) >= k)//注意這里是>=,因為是求第num - k + 1小的，所以盡量往左逼近r = mid - 1;elsel = mid + 1;}printf("%d\n", l);}}return 0; }

下面是LogN的方法

/*題意：某人養了很多貓，他會把一些貓合并成一組，并且會詢問第k大組有幾只貓算法：處理集合用并查集，動態更新第K值用樹狀數組，具體的看注釋2011-07-21 20:42 */#include <stdio.h>#define MAXN 300000int a[MAXN], c[MAXN + 5], f[MAXN]; int n, m;int lowbit(int x) {return x & -x; }int find(int x) {if (x != f[x])f[x] = find(f[x]);return f[x]; }void add(int x, int num) {for ( ; x <= MAXN; x += lowbit(x))c[x] += num; }int sum(int x) {int sum = 0;for ( ; x > 0; x -= lowbit(x))sum += c[x];return sum; }/*求第K小的值。a[i]表示值為i的個數，c[i]當然就是管轄區域內a[i]的和了。神奇的方法。不斷逼近。每次判斷是否包括（ans，ans + 1 << i]的區域，不是的話減掉，是的話當前的值加上該區域有的元素。注意MAXN是更新到的最大值，如果上面只更新到n的話取n就行了。乍一看循環的量是常數，難道是O（1）的嗎？實際上i應該遍歷到LogN，所以該算法是LogN的。比線段樹、平衡樹代碼量少多了。 */int find_kth(int k) {int ans = 0, cnt = 0, i;for (i = 20; i >= 0; i--){ans += (1 << i);if (ans >= MAXN|| cnt + c[ans] >= k)ans -= (1 << i);elsecnt += c[ans];}return ans + 1; }int main() {int i, num, cmd, x, y, k, l, r;scanf("%d%d", &n, &m);for (i = 1; i <= n; i++)f[i] = i;for (i = 1; i <= n; i++)a[i] = 1;add(1, n);//a[i]表示組內有i只貓的組數num = n;for (i = 1; i <= m; i++){scanf("%d", &cmd);if (cmd == 0){scanf("%d%d", &x, &y);x = find(x);y = find(y);if (x == y)continue;add(a[x], -1);add(a[y], -1);add(a[y] = a[x] + a[y], 1);f[x] = y;num--;//合并集合}else{scanf("%d", &k);printf("%d\n", find_kth(num - k + 1));//第k大就是第num - k + 1小的}}return 0; }

4.“圖騰”類問題的統計

這個例題很多，就說一個求逆序對的吧；

1、什么是逆序數？

???????? 在一個排列中，如果一對數的前后位置與大小順序相反，即前面的數大于后面的數，那么它們就稱為一個逆序。一個排列中逆序數的總數就是這個排列的逆序數。

?

2、用樹狀數組求逆序數的總數

???????? 2.1該背景下樹狀數組的含義

???????? 我們假設一個數組A[n],當A[n]=0時表示數字n在序列中沒有出現過，A[n]=1表示數字n在序列中出現過。A對應的樹狀數組為c[n],則c[n]對應維護的是數組A[n]的內容，即樹狀數組c可用于求A中某個區間的值的和。

???????? 樹狀數組的插入函數(假設為 void insert(int i,int x) )的含義：在求逆序數這個問題中，我們的插入函數通常使用為insert( i , 1 )，即將數組A[i]的值加1 (A數組開始應該初始化為0，所以也可以理解為設置A[ i ]的值為1，即將數字i 加入到序列的意思 )。，同時維護c數組的值。

???????? 樹狀數組中區間求和函數(假設函數定義為： int getsun(int i ) )的含義：該函數的作用是用于求序列中小于等于數字 i 的元素的個數。這個是顯而易見的，因為樹狀數組c 維護的是數組A的值，則該求和函數即是用于求下標小于等于 i 的數組A的和，而數組A中元素的值要么是0要么是1，所以最后求出來的就是小于等于i的元素的個數。

???????? 所以要求序列中比元素a大的數的個數，可以用i - getsum(a)即可( i 表示此時序列中元素的個數)。

?

???????? 2.2如何使用樹狀數組求逆序數總數

???????? 首先來看如何減小問題的規模:

???????? 要想求一個序列 a b c d,的逆序數的個數，可以理解為先求出a b c的逆序數的個數k1，再在這個序列后面增加一個數d，求d之前的那個序列中值小于d的元素的個數k2，則k1+k2即為序列a b c d的逆序數的個數。

???????? 舉個例子加以說明：

　　假設給定的序列為 4 3 2 1，我們從左往右依次將給定的序列輸入，每次輸入一個數temp時，就將當前序列中大于temp的元素的個數計算出來，并累加到ans中，最后ans就是這個序列的逆序數個數。

?

序列的變化(下劃線為新增加元素)	序列中大于新增加的數字的個數	操作
{ }	0	初始化時序列中一個數都沒有
{4?}	0	往序列中增加4，統計此時序列中大于4的元素個數
{4?3?}	1	往序列中增加3，統計此時序列中大于3的元素個數
{4 3?2}	2	往序列中增加2，統計此時序列中大于2的元素個數
{4 3 2?1}	3	往序列中增加1，統計此時序列中大于1的元素個數

???????? 當所有的元素都插入到序列后，即可得到序列{4 3 2 1}的逆序數的個數為1+2+3=6.

????????

???????? 2.3 C++實現代碼如下：

#include <iostream> #include <string> using namespace std; #define N 1010 int c[N]; int n; int lowbit(int i) {return i&(-i); } int insert(int i,int x) {while(i<=n){c[i]+=x;i+=lowbit(i);}return 0; }int getsum(int i) {int sum=0;while(i>0){sum+=c[i];i-=lowbit(i);} return sum; } void output() {for(int i=1;i<=n;i++) cout<<c[i]<<" ";cout<<endl; } int main() {while(cin>>n){int ans=0;memset(c,0,sizeof(c));for(int i=1;i<=n;i++){int a;cin>>a;insert(a,1);ans+=i-getsum(a);//統計當前序列中大于a的元素的個數}cout<<ans<<endl;}return 0; }

我們會發現要是這里的a很大，那怎么辦；這里的a相當于A[a]下標。這時候我們就要用到離散化了。（不懂離散化的--點擊離散化的思想）

?

知道什么是逆序對后就好辦了，樹狀數組的功能就是可以單點更新，區間查詢，這樣你把每個數該在的位置離散化出來，然后每次把每個數該在的位置上加上1，比如一個數該在的位置為x，那么用add(x)把這個位置加上1，然后再用區間查詢read(x)查詢1~x的和，也就是可以知道前面有多少個數是比他小的了（包括那個數自己），再用已經插入的數的個數減去read(x)，就算出了前面有多少個數比他大了。

下面舉個例子來詳細的看一下過程：

第一次插入的時候把5這個位置上加上1，read(x)值就是1，當前已經插入了一個數，所以他前面比他大的數的個數就等于 i - read(x) = 1 - 1 = 0，所以總數 sum += 0

?

第二次插入的時候，read(x)的值同樣是1，但是 i - read(x) = 2 - 1 = 1，所以sum += 1

第三次的時候，read(x)的值是2，i - read(x) = 3 - 2 = 1，所以sum += 1

第四次，read(x)的值是1，i - read(x) = 4 - 1 = 3，所以sum += 3

第五次，read(x)的值是1，i - read(x) = 5 - 1 = 4，所以sum += 4

這樣整個過程就結束了，所有的逆序對就求出來了。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std;int n,tree[100010]; void add(int k,int num) {while(k<=n){tree[k]+=num;k+=k&-k;} }int read(int k) {int sum=0;while(k){sum+=tree[k];k-=k&-k;}return sum; } struct node {int val,pos; }a[100010]; bool cmp(node a,node b) {return a.val < b.val; } int main(void) {int i,j;int b[100010];while(scanf("%d",&n)==1){memset(tree,0,sizeof(tree));for(i=1;i<=n;i++){scanf("%d",&a[i].val);a[i].pos = i;}sort(a+1,a+1+n,cmp);int cnt = 1;for(i=1;i<=n;i++){if(i != 1 && a[i].val != a[i-1].val)cnt++;b[a[i].pos] = cnt;}LL sum = 0;for(i=1;i<=n;i++){add(b[i],1);sum += (i - read(b[i]));}printf("%lld\n",sum);}return 0; }

?

總結

以上是生活随笔為你收集整理的树状数组的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。