线段树常见错误快速检查清单
查看原帖
线段树常见错误快速检查清单
612722
JustPureH2O楼主2024/8/8 14:33

搜集了讨论区出现的一些常见错误,加上我个人犯的错误,整理而成的快速检查清单:

pushdown 部分:

  1. 左右儿子的标记也需更新
  2. 注意标记的下放顺序:区间已经有推平时,下放翻转标记则需把推平标记异或 11;如果区间已经存在翻转标记,下放推平标记时则需清空翻转标记,翻转时要么改推平标记要么改翻转标记,不要两者都改
  3. 如果你的推平标记初始值是非零的(例如我设置成 −1-1),那么在判断是否存在推平标记时不能使用 if (tree[idx].tag) 这样的语句,而是 if (tree[idx].tag >= 0)(−1-1 也会返回 true)
  4. 注意区间翻转交换的是同一个子树同一个方向上 00 和 11 的最大连续数。
  5. 标记是异或,不要赋值成 11

pushup 部分:

  1. 如果你做维护最大子段和的题做多了,请注意此处维护区间最长左/右连续数量时需要判断能否跨区间合并(如果你的最大连续数查询函数返回一个线段树,那么查询维护过程同理)

数值查询部分:

  1. 开头需要 pushdown
  2. 如果你查询 1 的个数时选择返回数字,那么请用 if (l <= mid) return findLeft 的形式;如果你查询最大连续数量时返回一个线段树结构体,那么请用 if (l > mid) return findRight

区间修改部分:

  1. 开头需要 pushdown
  2. 当前区间被完全包含,需要给当前编号打标记,同时更新当前的信息,并 return
  3. 结尾需 pushup

建树部分:

  1. 不要忘记维护两种数的最大连续长度,把所有信息维护完
  2. 不要忘了 return
  3. 如果你使用结构体存储左右节点的下标,注意 mid 的计算方式可能略有不同

主函数/全局定义部分:

  1. 线段树开四倍空间
  2. 操作时读入的下标从 00 开始
  3. 不要忘记 build
  4. 最好把标记分开存

祝AC

2024/8/8 14:33
加载中...