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