alpc60 ACM/ICPC程序设计
成长的路……源
posts - 20,comments - 42,trackbacks - 0
 

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]

其中ki的二进制表示末尾0的个数,所以2^k即为i的二进制表示的最后一个1的权值.

可以把树状数组看作是把数组分成了若干个2^k大小的空间。对于一个下标ic[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)来计算。

 

 

       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的个数,这个用树状数组实现。扫描一遍可得出结果。

 

 

       2155 Matrix n*n01矩阵,两种操作,1、翻转矩形(x1,y1(x2,y2)的值,2、输出位置为(x,y)矩阵处的值。先考虑一维的情况,设A<B,那么要翻转[A,B]之间的值,可以分解为两步操作,先翻转[1,A-1],然后再翻转[1,B],其中翻转的次数就可以用树状数组来计算。然后再将次操作扩展到二维的情形,只需将x方向与y方向套成一个二重循环即可。从这里我们也可以看到树状数组处理类似问题时比线段树的优越性。从代码的长度,空间消耗上面,树状数组都有明显的优势。

posted on 2008-09-24 16:35 飞飞 阅读(3371) 评论(2)  编辑 收藏 引用 所属分类: ACM/ICPC

FeedBack:
# re: 树状数组学习心得
2009-07-04 16:43 | Mr.moon
2481 cows if(p[i].y > max_n) max_n=p[i].y;
---------------------------------------------
好像应该是p[i].x
  回复  更多评论
  
# re: 树状数组学习心得
2012-07-16 22:26 | twocoldz
apple tree有点不明白的地方
为什么 ans=high[a]-low[a]+1+Sum(high[a])-Sum(low[a]-1)
这个想半天没明白啊  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理