前言

果果终于讲线段树了
线段树太 TM 好用啦！
But，强大的功能是需要码量来实现的。

定义

线段树是一种储存了一个序列的区间信息，并在各个区间中建立了关联的数据结构。
对于任意一个序列都可以建出它的线段树。

它是一颗完全二叉树，它的每一个节点都是一个区间。
对于每一个节点，其左儿子节点为这段区间的左半部分，右儿子节点为这段区间的右半部分。
而且由于是完全二叉树，其根节点的编号为 \(1\)，对于每一个节点 \(p\)，其左儿子节点编号为 \(2p\)，右儿子节点编号为 \(2p + 1\)。这种编号方便我们遍历线段树。

如下图就是一颗线段树：

根据定义，这样就可以建一颗线段树：

#define ls(x) (x * 2)
#define rs(x) (x * 2 + 1)
struct node {
	int l, r, val;
	// l : 左端点
	// r : 右端点
	// val : 区间信息
}tr[N * 4];
void build(int p, int l, int r) {
	if(l == r) {tr[p] = node{l, r, \*somevalue*\};return;} // 叶节点特殊处理
	int mid = (l + r) >> 1;
	build(ls(p), l, mid); // 递归建立左右子区间
	build(rs(p), mid + 1, r);
	tr[p] = node{l, r, tr[ls(p)].val \*someopt*\ tr[rs(p)].val}; // 这里合并两个子区间的信息
}

线段树可以在 \(\text{O}(\log n)\) 的时间复杂度中实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。