我认为无论怎么样，在需要访问子区间的时候，上面有的标记都应该先 pushdown。
#3393 巨(mu)型(ban)线段树
Forgive_jkxjkx1031 edited 7 年，1 月前
线段树最基本的两种操作——段增加和段覆盖，放在一起之后，就如同干柴遇到烈火(?)一般，令人欲仙欲死......谁做谁知道......
段增加和段覆盖结合之后，有以下几点需要注意：
1. 决定一个区间上同时存在 add 标记和 set 标记时，是 set 覆盖 add，还是在 set 基础上再 add？（我选择了后者，以避免 add 标记无处可 “pushdown” 的情况）
2. 更新时，add 标记和 set 标记都需要 pushdown。因为 set 标记以下的 add 标记是无效的（所以要 pushdown set），一个区间被 set 之后该区间以上的 add 标记也是无效的（所以要 pushdown add）。
3. 基于第2点，段增加和段覆盖的程序代码其实是非常相似的，因此可以将两种操作的代码合并为一个函数，以减少代码量。
4. pushdown 操作时，带有 set 标记的 pushdown 和不带有 set 标记的 pushdown 是不同的。如果将 set 标记和 add 标记一起 pushdown ，必须清空子区间原来的 add 标记（这种情况下 add 标记其实和 set 标记效果是相同的）；如果只将 add 标记 pushdown，则应将该 add 标记的值累加到子区间的 add 标记上。
这么做确实可以，但是如果只有 add 标记，pushdown 是不是没什么意义呢？因为不论有没有 pushdown，query 的时候都必须要统计一条链上所有 add 之和，而不是像处理 set 标记那样递归到第一个有效 set 标记出现即止。