线段树

线段树的五个操作：

• 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$ 数量级。

例题：最大数