POJ 3321 Apple Tree

http://acm.pku.edu.cn/JudgeOnline/problem?id=3321

POJ 2481 Cows

http://acm.pku.edu.cn/JudgeOnline/problem?id=2481

POJ 2155 Matrix

http://acm.pku.edu.cn/JudgeOnline/problem?id=2155

       今天在POJ淘了這幾道題目，學習了一下樹狀數組的用法，跟大家分享一下心得。可以把樹狀數組看成一種數據結構，對于一個數組，如果有多次操作，每次的操作有兩種：1、修改數組中某一元素的值，2、求和，求數組元素a[1]+a[2]+…a[num]的和。這是樹狀數組最基本的應用了，用樹狀數組可以實現O(log(n))的修改以及O(log(n))的求和。當然用線段樹完全可以勝任這些計算，但是線段樹寫起來代碼比較長，并且線段樹要占用2*n大小的空間。下面先給出樹狀數組的三個基本操作的函數：

int lowbit(int k)

{

       return k&(-k);

}

//lowbit函數是計算k的二進制位最低位不為0的數字的權值。

void Modify(int num, int v)

{

       while(num <= n)

       {

              c[num]+=v;

              num+=lowbit(num);

       }

}

//Modify函數是往數組c中修改值，更新整個數組的值，實現了操作1；

int Sum(int num)

{

       int ans=0;

       while(num > 0)

       {

              ans+=c[num];

              num-=lowbit(num);

       }

       return ans;

}

//Sum函數返回數組元素a[1]+a[2]+…a[num]的和，實現操作2；

       樹狀數組的巧妙之處在于對于數組下標的二進制的操作，假設a[1...N]為原數組,定義c[1...N]為對應的樹狀數組:

c[i] = a[i - 2^k + 1] + a[i - 2^k + 2] + ... + a[i]

其中k為i的二進制表示末尾0的個數,所以2^k即為i的二進制表示的最后一個1的權值.

可以把樹狀數組看作是把數組分成了若干個2^k大小的空間。對于一個下標i，c[i]的值是由i/(lowbit(i))個數組元素的值所組成的，每次步進的單位是k=lowbit(i)，這個有點像二分歸并的思想！這樣就可以實現O(log(n))的修改和查詢。

       下面是樹狀數組的具體應用：

       3321 Apple Tree 一棵樹上長了蘋果，每一個樹枝節點上有長蘋果和不長蘋果兩種狀態，兩種操作，一種操作能夠改變樹枝上蘋果的狀態，另一種操作詢問某一樹枝節點一下的所有的蘋果有多少。具體做法是做一次dfs，記下每個節點的開始時間low[i]和結束時間high[i]，那么對于i節點的所有子孫的開始時間和結束時間都應位于low[i]和high[i]之間，另外用一個數組c[i]記錄附加在節點i上的蘋果的個數，然后用樹狀數組統計low[i]到high[i]之間的附加蘋果總數。這里用樹狀數組統計區間可以用Sum(high[i])-Sum(low[i]-1)來計算。

 1#include <stdio.h>
 2#include <string.h>
 3#include <vector>
 4using namespace std;
 5
 6//vector<int> g[100005];
 7struct Node
 8{
 9    int v;
10    struct Node *next;
11}g[100005];
12int n,m,cnt,low[100005],high[100005],c[100005],flag[100005];
13bool mark[100005];
14
15void dfs(int v)
16{
17    struct Node *p=g[v].next;
18    mark[v]=true;
19    cnt++;
20    low[v]=cnt;
21    while(p)
22    {
23        if(!mark[p->v])
24            dfs(p->v);
25        p=p->next;
26    }
27    high[v]=cnt;
28}
29int lowbit(int k)
30{
31    return k&(-k);
32}
33void Modify(int num, int v)
34{
35    while(num <= n)
36    {
37        c[num]+=v;
38        num+=lowbit(num);
39    }
40}
41int Sum(int num)
42{
43    int ans=0;
44    while(num > 0)
45    {
46        ans+=c[num];
47        num-=lowbit(num);
48    }
49    return ans;
50}
51
52int main()
53{
54    int i,j,a,b,ans;
55    char temp[10];
56    struct Node *p;
57    //freopen("in.txt","r",stdin);
58    scanf("%d",&n);
59    memset(g,0,sizeof(g));
60    for(i=1; i<n; i++)
61    {
62        scanf("%d%d",&a,&b);
63        p=new Node;
64        p->next=g[a].next;
65        p->v=b;
66        g[a].next=p;
67        p=new Node;
68        p->next=g[b].next;
69        p->v=a;
70        g[b].next=p;
71    }
72    memset(mark,false,sizeof(mark));
73    memset(c,0,sizeof(c));
74    for(i=1; i<=n; i++)
75        flag[i]=1;
76    cnt=0;
77    dfs(1);
78    scanf("%d",&m);
79    while(m--)
80    {
81        scanf("%s",temp);
82        if(temp[0] == 'Q')
83        {
84            scanf("%d",&a);
85            ans=high[a]-low[a]+1+Sum(high[a])-Sum(low[a]-1);
86            printf("%d\n",ans);
87        }
88        else
89        {
90            scanf("%d",&a);
91            if(flag[a]) Modify(low[a],-1);
92            else Modify(low[a],1);
93            flag[a]^=1;
94        }
95    }
96    return 0;
97}
98
99

       2481 Cows 給n個區間[Si,Ei]，區間[Sj,Ej]< [Si,Ei] 有 Si <= Sj and Ej <= Ei and Ei - Si > Ej – Sj。按y坐標從小到達，x坐標從大到小的順序排序，然后從后往前掃描，記錄i之前所有的j區間Sj<Si的個數，這個用樹狀數組實現。掃描一遍可得出結果。

 1#include <stdio.h>
 2#include <string.h>
 3#include <algorithm>
 4using namespace std;
 5
 6struct P
 7{
 8    int x,y,id;
 9}p[100005];
10int n,a[100005],max_n,b[100005];
11
12int lowbit(int k)
13{
14    return k&(-k);
15}
16void Modify(int num, int v)
17{
18    while(num <= max_n)
19    {
20        a[num]+=v;
21        num+=lowbit(num);
22    }
23}
24int Sum(int num)
25{
26    int ans=0;
27    if(num <= 0) return 0;
28    while(num)
29    {
30        ans+=a[num];
31        num-=lowbit(num);
32    }
33    return ans;
34}
35bool operator <(const P a, const P b)
36{
37    if(a.y == b.y) return a.x > b.x;
38    return a.y < b.y;
39}
40
41int main()
42{
43    int i;
44    //freopen("in.txt","r",stdin);
45    while(scanf("%d",&n), n)
46    {
47        max_n=0;
48        for(i=0; i<n; i++)
49        {
50            scanf("%d%d",&p[i].x,&p[i].y);
51            p[i].id=i;
52            p[i].x++;
53            p[i].y++;
54            if(p[i].y > max_n) max_n=p[i].y;
55        }
56        sort(p,p+n);
57        memset(a,0,sizeof(a));
58        for(i=n-1; i>=0; i--)
59        {
60            if(i != n-1 && p[i].y == p[i+1].y && p[i].x == p[i+1].x)
61                b[p[i].id]=b[p[i+1].id];
62            else
63                b[p[i].id]=Sum(p[i].x);
64            Modify(p[i].x,1);
65        }
66        for(i=0; i<n; i++)
67        {
68            if(i) printf(" ");
69            printf("%d",b[i]);
70        }
71        printf("\n");
72    }
73    return 0;
74}
75
76

       2155 Matrix 有n*n的0，1矩陣，兩種操作，1、翻轉矩形（x1,y1）(x2,y2)的值，2、輸出位置為(x,y)矩陣處的值。先考慮一維的情況，設A<B，那么要翻轉[A,B]之間的值，可以分解為兩步操作，先翻轉[1,A-1]，然后再翻轉[1,B]，其中翻轉的次數就可以用樹狀數組來計算。然后再將次操作擴展到二維的情形，只需將x方向與y方向套成一個二重循環即可。從這里我們也可以看到樹狀數組處理類似問題時比線段樹的優越性。從代碼的長度，空間消耗上面，樹狀數組都有明顯的優勢。

 1#include <stdio.h>
 2#include <string.h>
 3
 4int a[1005][1005],n,m;
 5
 6int lowbit(int k)
 7{
 8    return k&(-k);
 9}
10void Modify(int x1, int y1, int x2, int y2)
11{
12    int i,j;
13    for(i=x1-1; i>0; i-=lowbit(i))
14    {
15        for(j=y1-1; j>0; j-=lowbit(j))
16        {
17            a[i][j]^=1;
18        }
19        for(j=y2; j>0; j-=lowbit(j))
20        {
21            a[i][j]^=1;
22        }
23    }
24    for(i=x2; i>0; i-=lowbit(i))
25    {
26        for(j=y1-1; j>0; j-=lowbit(j))
27        {
28            a[i][j]^=1;
29        }
30        for(j=y2; j>0; j-=lowbit(j))
31        {
32            a[i][j]^=1;
33        }
34    }
35}
36int Sum(int x, int y)
37{
38    int ans=0,i,j;
39    for(i=x; i<=n; i+=lowbit(i))
40    {
41        for(j=y; j<=n; j+=lowbit(j))
42            ans^=a[i][j];
43    }
44    return ans;
45}
46
47int main()
48{
49    int i,j,x1,x2,y1,y2,cases,ic=0;
50    char temp[10];
51    //freopen("in.txt","r",stdin);
52    scanf("%d",&cases);
53    while(cases--)
54    {
55        if(ic++) printf("\n");
56        scanf("%d%d",&n,&m);
57        memset(a,0,sizeof(a));
58        while(m--)
59        {
60            scanf("%s",temp);
61            if(temp[0] == 'C')
62            {
63                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
64                Modify(x1,y1,x2,y2);
65            }
66            else
67            {
68                scanf("%d%d",&x1,&y1);
69                printf("%d\n",Sum(x1,y1));
70            }
71        }
72    }
73    return 0;
74}
75
76