现在的位置: 首页 > 综合 > 正文

线段树总结

2017年04月21日 ⁄ 综合 ⁄ 共 745字 ⁄ 字号 评论关闭

T1、序列操作

http://blog.csdn.net/willinglive/article/details/37921297

1.两个lazy标记时,不能同时存在,pushdown中要消

2.任何询问调用pushdown保证L<=R!!!

3.pushdown尽量不要写在前面(这样我从来就没调对过),lazy表示当前节点已经修改

T2、wikioi 行星序列

1.对lazy操作的进一步理解,与T1不同,两个lazy可以同时存在(此题彻底颠覆了对lazy的理解),lazy的合并操作

2.注意k和b可以取模,k和b的合并要细心

T3、tyvj 小白逛公园

http://blog.csdn.net/willinglive/article/details/38065327

线段树合并的更深一步的理解,改代码完全不用担心询问操作跨越左右儿子区间的询问问题

这个代码是错的:

maxs:最大子区间和

maxs[p]=max(maxs[l],maxs[r]);

maxs[p]=max(maxs[p],max(maxr[l],0)+max(maxl[r]),0));

问什么呢?这个问题早在“序列操作”一题中就遇到过,询问可能跨越了左右儿子,不过“序列操作”太巧了,刚好能解决,不过这个题不行了

这个代码的巧妙之处就在于完全不用担心序列的合并问题,因为询问操作函数的类型是一个线段,合并的也是线段

这就更体现了线段树的实质

也就是说线段树左右儿子的全包含合并能实现,但半包含合并不能实现时,可以用这个方法了

不过这样的话只能用struct了,牺牲了点速度

目测不影响lazy

线段树不能实现的:

1.翻转区间(平衡树)

2.统计区间大于k的个数(特别小的范围可以手动,比较小的范围用二位BIT或者SegTree)

3.区间开方(见上帝一题)

【上篇】
【下篇】

抱歉!评论已关闭.