这是我写的第一道线段树,思路还算清晰,不过之前走了不少弯路。
主要错在:误以为线段树是一棵满二叉树,建树时吃了苦头。//线段树除了最后一层可能不满足满二叉树性质外,上面的所有层构成完全二叉树,因此仍然可以用满二叉树的性质:如果树根节点从1开始编号,则对任意编号的节点t,左子树编号为t*2,右子树编号为t*2+1,父节点编号为t/2。这样,建树的时候节点内就不用记录儿子或父节点的信息了。
下面结合poj3264说一下我对线段树的理解。
题意描述:随即给定N个奶牛(<=50000)的身高,奶牛按输入顺序编号,接下来

有Q次(<=2E5)查询,每次查询时给定两个编号a,b,要求给出编号在[a, b]之间

奶牛的身高最大差值。
要用线段树的原因很明显,线性查找一定超时。
下面是我的解题思路:
建树
建树过程很简单,先建左右子树,再建双亲。注意节点中信息的更新。
查询
查询过程可分为四种情况
假设节点表示的区间为[a, b],要查询的区间为[aa, bb],mid = (a+b)/2.
情况1.[aa, bb]区间正好是[a,b]区间。
情况2.[aa, bb]区间在[a, mid]区间内。
情况3.[aa, bb]区间在[mid+1, b]区间内。
情况3.[aa, bb]区间一部分在[a, mid]区间内,一部分在[mid+1, b]区间内。这种情况下需要有合并过程。也就通过比较从两部分中选出min和max。
一些细节:据说动态分配内存可能超时,所以这里用了一个数组A[]来作为开辟空间的区域。
以下是本题的代码:


下面是利用了满二叉树性质的代码:(同样的代码用java就超时,C++ 1563MS AC,java和C++的效率差距真的有这么大吗)

利用满二叉树性质的代码


 

Java的超时代码

 

posted on 2012-07-29 10:44 小鼠标 阅读(1848) 评论(2)  编辑 收藏 引用 所属分类: 数据结构

FeedBack:
# re: 线段树
2015-04-17 15:17 | 伤心的笔
对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。  回复  更多评论
  
# re: 线段树
2015-04-17 15:32 | 小鼠标
是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
加油,祝你好运啦!  回复  更多评论
  

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


<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜