线段树基础

线段树是一种常用的用来维护区间信息的数据结构。

具体来讲，线段树是一棵树，每一个节点都维护一个区间的信息和。

线段树可以如此递归定义：

1. 根节点 $1$ 维护的区间是 $[1, n]$。

2. 设当前节点维护的区间是 $[l, r]$。如果 $l = r$，则它是叶节点；

3. 否则它有两个儿子，分别维护区间 $[l, \lfloor\frac{l + r}{2}\rfloor]$ 和 $[\lfloor\frac{l + r}{2}\rfloor + 1, r]$。

下面的图详细的描述了线段树。

显然，除了最后一层，整棵线段树是一棵完全二叉树。于是，我们可以直接使用 $2x$ 和 $2x + 1$ 来表示 $x$ 的两个儿子，于是只需要一个数组就可以存下这颗线段树。

注意，线段树数组一定要开到 $4n$！！！

懒标记实现区间修改

线段树技巧

动态开点

线段树合并

线段树应用

扫描线

例题