线段树的抉择

zerol edited 7 年，1 月前

• 要不要把元素个数 n 补成 2 的幂？ 这个无所谓，但如果自底向上，那么还是需要的。
• pushdown 之后要不要马上 maintain？ 可以不用，用的话会慢一些。
• query 的时候要不要 pushdown？ 如果不要的话，查询时应该把之前访问到的结点的标签累加起来（特指 add）。如果要的话，代码会更加清晰一些。
• maintain 的时候是否考虑当前结点的标签？ 如果考虑了，查询的时候就不要考虑当前结点标签了。

• query 的时候先考虑 set 标签还是先考虑查询区间包含当前区间？都可以，但是先考虑 set 会快一些。

• 函数名怎么取？

• 要不要封装？

当然是都可以啦

注意事项：

• maintain 保证即使重复调用 maintain 也不会出错，尤其是 maintain 叶节点的时候
• pushdown 之后肯定要 maintain 子节点，无论有没有递归下去
• set 标签 pushdown 后 add 标签要清空

最后附两份刘汝佳代码

• https://github.com/klb3713/aoapc-book/blob/master/TrainingGuide/bookcodes/ch3/uva11992.cpp
• https://github.com/klb3713/aoapc-book/blob/master/TrainingGuide/bookcodes/ch3/uva11992b.cpp

Comments

ultmaster

7 年，1 月前

不久之后大家都只会 set+add 的这一种线段树了。。。（反而是用得最少的一种啊，先奶一口

回复 0 0

kblack

7 年，1 月前

不如再加一个历史最值的操作？不过那样就和bzoj3064一样了

回复 0 0