| WXYZ 的个人资料WXYZ的异人馆照片日志列表 |  工具  帮助 |
|
11月30日 线段树初级心得 一次做题，最重要的并不在于你做出了多少题，而在于你在这次比赛中有进步。因此我对上星期的POJ月赛非常满意。
这次月赛我只做出一题：E题。我一看，马上知道是线段树。可惜我虽然在很久以前就是好好学学线段树的想法，但久久没有实现。遇到这样一题，只好傻在那里。然后翻翻其它题，觉得除了B题还能想想外，其它暂时还差点。然后在攻B题两个小时后，还是以失败告终。这时我非常失望，竟然连一题也做不出来？然后下个决心，马上做E题，马上学线段树。
当即从网上找来一个线段树的论文+PPT，大概看了下，就开始写代码了。第一次写，卡了不久，终于写好了，提交下，超时。然后找出超时原因，修改提交，一个Wrong Answer。第一次写啊，这样的结果并不出乎我意料。然后就自己开始找数据检验代码了。不久找到一组，修改后，再次提交，还是Wrong Answer。改吧改吧，能完成就是很好的了。修改提交，终于Accepted了。当时无比兴奋啊，走遍各个知道我有做题的宿舍，逐个欢呼。我终于写出了第一个线段树了。
1、线段树之所以快，在于预处理，然后可以二分快速得出答案，对于多次区间操作的题特别适合。
2、由于线段树的特性，要使之快，必须在查询或修改某个区间并且此区间的首尾与线段树某段的首尾完全重合时，就必须终于再向深处递归（最多还可以再深一层），就必须在此区间上完成操作并且return，也正因为有这个才能保证线段树的log(n)时间。
3、构造线段树时，还须想清楚，在修改区间时，是否逐步修改，还是采用在统计时逐步统计。
4、在进行递归时，要想清楚这层递归与上下两层递之间的关系，怎样传递参数等。最好先考虑最底层，然后再逐步向上思考。
此为线段树初级心得，可以说是线段树最基本的东西吧。对于区间的插入与删除等，我还是不会，可能后来会有个中级或高级心得了。 评论 (3)
引用通告此日志的引用通告 URL 是： http://wxyz202.spaces.live.com/blog/cns!D4DC981555112325!566.trak 引用此项的网络日志
|
|
|
