线段树题,本题对线段树的操作有建树(MakeTree())、查找(Query())、更新(update())。
建树一次完成,时间花费为O(LogN);查询的时间复杂度鄙人还不会分析O(∩_∩)O~,最坏可能是O(N),不过这种情况应该很难出现;更新的算法值得商榷,不同的策略时间复杂度会相差很大。下面讲解两种比较用以想到的更新策略。
更新方法一:
每次都将所有能更新的节点更新,这种方式最坏情况下将会更新树中所有节点,此时时间复杂度为O(N)。本题使用这种方法会TLE。
更新方法二:
每次都尽量少的更新节点信息,与第一种方法相比,Node内会多一个变量en,我把它形象的称之为“势能”,计算结果时要将该的所有父节点的“势能”也考虑在内。这种方法的时间复杂度也不好分析,但明显优于第一种方法。
这一题对时间卡的很紧,主要是花在树的更新上。
关于线段树可以先参阅:http://www.cppblog.com/hoolee/archive/2012/07/29/185531.html
以下是本题代码:

posted on 2012-07-31 20:40 小鼠标 阅读(3610) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

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


<2012年3月>
26272829123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

随笔分类(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

阅读排行榜