线段树

线段树的五个操作：

• pushup()：由子节点来算父节点的信息；
• pushdown()：把当前父节点的信息下传到子节点，也称为懒标记(延迟标记)；
• build()：将一段区间初始化成线段树；
• modify()：修改数据：
  • 修改单点：
  • 修改区间：需要用pushdown()懒标记延时更新，较难；
• query()查询某个区间的信息(如最大值)。

线段树是一个完美二叉树，除了最后一层外是一个满二叉树(类似堆)，可以用一维数组来存整棵树。

一个节点编号为 \(x\)：

• 父节点： \(\lfloor \frac{x}{2} \rfloor\) 或x >> 1；
• 左儿子： \(2x\) 或x << 1；
• 右儿子： \(2x+1\) 或x << 1 | 1。

如果树的最后一层有 \(n\) 个点，则树总共最多有 \(2n+(2n-1)=4n-1\) 个点。经验上，线段树开的数组空间为 \(4n\)。

查询的区间数量在 \(4\log n\) 数量级。

例题：最大数